ウィルソンの定理とは、
任意の素数$p$について
という定理のことです。
\begin{equation}\large (p-1)!\equiv-1\pmod p\end{equation}
が成り立つ。
また、逆も成り立ち、
$2$以上の自然数$n$について
となります。
\begin{equation}\large (n-1)!\equiv-1\pmod n\end{equation}
が成り立つならば、$n$は素数である。
これらが成り立つことを確かめてみます。
$(p-1)!$は、$p-1$以下のすべての自然数を1つずつ掛け合わせる階乗を表し、
\[(p-1)!=(p-1)\times(p-2)\times(p-3)\times\cdots\times3\times2\times1\]
となります。
ウィルソンの定理
$(1)$が成り立つことを$p=2$のとき、$p=3$のとき、$p≧5$のときで場合分けして調べてみます。
$p=2$のとき
\[(2-1)!=1!=1\]
であり、
\[1\equiv-1\pmod2\]
なので、
\[(2-1)!\equiv-1\pmod2\]
となり、$(1)$が成り立つことがわかります。
$p=3$のとき
\[(3-1)!=2!=2\]
であり、
\[2\equiv-1\pmod3\]
なので、
\[(3-1)!\equiv-1\pmod3\]
となり、$(1)$が成り立つことがわかります。
$p≧5$のとき
まず、
\begin{align*}(p-1)!&=(p-1)\times(p-2)\times(p-3)\times\cdots\times3\times2\times1\\[0.5em]&=(p-1)\times(p-2)\times(p-3)\times\cdots\times3\times2\end{align*}
とし、$(p-2)(p-3)\cdots\times3\times2$の部分に着目します。
「互いに素な整数と素数の余りの性質」で示したように、$2$以上$p-2$以下の自然数は、掛け合わせると$p$で割ったときの余りが$1$になるような2つの自然数の組に分けられます。
したがって、$(p-2)\times(p-3)\times\cdots\times3\times2$の$(p-3)$個の自然数の積には
\begin{align*}(p-2)\times(p-3)\times\cdots\times3\times2&\equiv\overbrace{1\times1\times\cdots\times1\times1}^{\frac{p-3}{2}個}\pmod
p\\[0.5em]&\equiv1\pmod p\end{align*}
が成り立ち、
\[p-1\equiv-1\pmod p\]
より
\begin{align*}(p-1)!=(p-1)\times(p-2)\times(p-3)\times\cdots\times3\times2&\equiv-1\times1\pmod
p\\[0.5em]\therefore (p-1)!&\equiv-1\pmod p\end{align*}
となって、$(1)$が成り立つことがわかります。
以上より、ウィルソンの定理
任意の素数$p$について
が成り立つことがわかります。
\[\large (p-1)!\equiv-1\pmod p\]
例えば、$p=29$のとき、
\[28\equiv-1\pmod{29}\]
で、$2$以上$27$以下の自然数の中から選んだ2つの積で$29$で割ったときの余りが$1$になる組み合わせは
\begin{align*}(2,
15)&&2\times15&=30\equiv1\pmod{29}\\[0.5em](3,
10)&&3\times10&=30\equiv1\pmod{29}\\[0.5em](4,
22)&&4\times22&=88\equiv1\pmod{29}\\[0.5em](5,
6)&&5\times6&=30\equiv1\pmod{29}\\[0.5em](7,
25)&&7\times25&=175\equiv1\pmod{29}\\[0.5em](8,
11)&&8\times11&=88\equiv1\pmod{29}\\[0.5em](9,
13)&&9\times13&=117\equiv1\pmod{29}\\[0.5em](12,
17)&&12\times17&=204\equiv1\pmod{29}\\[0.5em](14,
27)&&14\times27&=378\equiv1\pmod{29}\\[0.5em](16,
20)&&16\times20&=320\equiv1\pmod{29}\\[0.5em](18,
21)&&18\times21&=378\equiv1\pmod{29}\\[0.5em](19,
26)&&19\times26&=494\equiv1\pmod{29}\\[0.5em](23,
24)&&23\times24&=552\equiv1\pmod{29}\end{align*}
となり、「互いに素な整数と素数の余りの性質」で示したように、$2$以上$27$以下の自然数がすべて1回ずつ組み合わせに現れています。
したがって、
\begin{align*}(29-1)!&=28!\\[0.5em]&=28\times27\times26\times25\\&\quad\times24\times23\times22\times21\\
&\quad\times20\times19\times18\times17\\
&\quad\times16\times15\times14\times13\\
&\quad\times12\times11\times10\times9\\
&\quad\times8\times7\times6\times5\\
&\quad\times4\times3\times2\\[0.5em]&=28\times(2\times15)\\
&\quad\times(3\times10)\times(4\times22)\\
&\quad\times(5\times6)\times(7\times25)\\
&\quad\times(8\times11)\times(9\times13)\\
&\quad\times(12\times17)\times(14\times27)\\
&\quad\times(16\times20)\times(18\times21)\\
&\quad\times(19\times26)\times(23\times24)\\[0.5em]&\textcolor{red}\equiv(-1)\times1^{13}\pmod{29}\\[0.5em]&\equiv-1\pmod{29}\end{align*}
となり、ウィルソンの定理が成り立っていることがわかります。ウィルソンの定理の逆
ウィルソンの定理は、
$2$以上の自然数$n$について、
$n$が素数ならば
という命題の形で書くことができ、その逆は
$n$が素数ならば
\[(n-1)!\equiv-1\pmod n\tag2\]
が成り立つ。
$2$以上の自然数$n$について、
$(2)$が成り立つならば、$n$は素数である。
となります。
$(2)$が成り立つならば、$n$は素数である。
これの真偽を調べてみます。
ウィルソンの定理の逆の対偶は
$2$以上の自然数$n$について、
$n$が合成数ならば、$(2)$は成り立たない。
となります。
$n$が合成数ならば、$(2)$は成り立たない。
自然数$n$が合成数ということは、正の約数を3個以上、すなわち$1$と$n$以外に1個以上もっているということです。
$n$が正の約数を3個だけもつ合成数のとき
$n$が正の約数を3個だけもつ、すなわち$1$と$n$以外に1個だけ正の約数をもっているとき、$n$は素数の平方数となり、$n=p^2$（$p:$素数）と表せます。
ここで、$n=p^2=p\cdot p$であることより、$n$より小さい正の$p$の倍数は
ゆえに、$(n-1)!$では、これら$p-1$個の$p$の倍数が掛け合わされていることになります。
\[p, 2p, 3p, \cdots, (p-3)p, (p-2)p, (p-1)p\]
の$p-1$個あり、これらは$n-1$以下の自然数に含まれます。ゆえに、$(n-1)!$では、これら$p-1$個の$p$の倍数が掛け合わされていることになります。
$p=2$のとき
このとき、$n=4$で$(n-1)!$には$2$の倍数は1個しかありません。
そこで、$n=1$のときと同じ方法で調べると、
\[(4-1)!=3!=6\]
であり、
\[6\equiv2\pmod4\]
なので、$(2)$は成り立たないことがわかります。
$p≧3$のとき
このとき、$(n-1)!$で掛け合わせる自然数の中に$p$の倍数を2個以上含みます。
したがって、$(n-1)!$は少なくとも$p^2$の倍数である、すなわち$n$の倍数なので、
\[(n-1)!\equiv0\pmod n\]
となり、$(2)$は成り立たないことがわかります。
よって、$n$が正の約数を3個だけもつ合成数のとき、$(2)$は成り立たないことがわかります。
$n$が正の約数を4個以上もつ合成数のとき
$n$の正の約数を小さい順に並べたとき、$1$の次に大きい約数を$a$、$n$の次に小さい約数を$b$とおきます。なお、$a≠b$となります。
このとき、
\[ab=n\]
が成り立ち、$a,
b$はともに$(n-1)!$で掛け合わせる自然数の中に含まれています。
したがって、$(n-1)!$は少なくとも$n$の倍数なので、
\[(n-1)!\equiv0\pmod n\]
となり、$(2)$は成り立たないことがわかります。
以上より、$n$が合成数のとき、$(2)$は成り立たないので、ウィルソンの定理の逆の対偶
$2$以上の自然数$n$について、
$n$が合成数ならば、$(2)$、すなわち$(n-1)!\equiv-1\pmod n$は成り立たない。
が真となり、対偶の性質より、ウィルソンの定理の逆
$n$が合成数ならば、$(2)$、すなわち$(n-1)!\equiv-1\pmod n$は成り立たない。
$2$以上の自然数$n$について、
$(n-1)!\equiv-1\pmod n$が成り立つならば、$n$は素数である。
が真であることがわかります。
$(n-1)!\equiv-1\pmod n$が成り立つならば、$n$は素数である。
ウィルソンの定理とその逆より、$2$以上の自然数$n$が素数であることと$(n-1)!\equiv-1\pmod
n$が成り立つことは同値であることがわかります。
したがって、
\[\large (n-1)!\equiv-1\pmod n\]
が成り立つかを調べることを、素数判定として利用することができます。
ただし、$n$が大きいほど$(n-1)!$の計算が難しくなります。
(2026/9)内容を修正しました。
Share:
