ウィルソンの定理

今回は正整数が素数であるための条件であるウィルソンの定理を証明しますが、その前に少し準備をします。$m$ を合成数として、$(m-1)\,!$ を $m$ で割ったときの余り
\[(m-1)\,!\quad\mathrm{mod}\quad m\]
を考えてみます。たとえば $n=8$ のときは
\[(8-1)\,!=7!=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\]
となりますが、$8=2\cdot 4$ と考えると、$(8-1)\,!$ の因数の中に必ず $2$ と $4$ が含まれるので $8$ で割り切れます。すなわち
\[(8-1)\,!\equiv 0\quad (\mathrm{mod}\:8)\]
となります。このように平方数でない合成数を適当な 2 数 $a,\;b\:(1\gt a\gt b\gt m)$ の積に分解すると
\[(m-1)\,!=(m-1)\cdot (m-2)\:\cdots\:a\:\cdots\:b\:\cdots\:2\cdot 1\]
の中に必ず $a,\:b$ が含まれるので、
\[(m-1)\,!\equiv 0\quad (\mathrm{mod}\:m)\]
となります。$m$ が平方数 $a^2$ である場合は少しだけ複雑になります。たとえば $m=9=3^2$ の場合は
\[(9-1)\,!=8!=8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\]
となりますが、因子の１つが $6=2\cdot 3$ なので、$(9-1)\,!$ の中に $3$ が２つ含まれていることになり、$(9-1)\,!$ は $9$ で割り切れます：
\[(9-1)\,!\equiv 0\quad (\mathrm{mod}\:9)\]
これは $9-1\geq 2\cdot 3$ であるから割り切れたのです。そんなことは、ほとんど自明であるように思えますが、こうならない例が１つだけあるのです。それは $m=4=2^2$ のときで、
\[(4-1)\,!=3\cdot 2\cdot 1\]
ですから、$4-1\lt 2\cdot 2$ であるために、$(4-1)\,!$ の中に $2$ という因子は１つしか含まれておらず、$4$ で割り切ることができません。
\[(4-1)\,!\not\equiv 0\quad (\mathrm{mod}\:4)\]
念のために、こういう例外が $m=4$ だけなのかどうかを確認しておきます。

$m=a^2$ とおくと、
\[(a^2-1)\,!=(a^2-1)\cdot (a^2-2)\cdots a\cdots 2\cdot 1\]
であり、この中に $2a$ が含まれる条件は
\[a^2-1\geq 2a\]
ですから、この 2 次不等式を解いて（もちろん $a$ は正数です）
\[a\geq 1+\sqrt{2}\]
すなわち $a\gt 3$ のときに $(a^2-1)\,!$ は $a^2$ で割り切れることになります。
以上をまとめると、

ウィルソンの定理

本題はここからです。$p$ を素数としたときに $(p-1)\,!$ を $p$ で割ったときの余りはいくらになるかを考えます。たとえば $p=7$ のときに $(7-1)\,!$ を計算すると
\[(7-1)\,!=6!=720\equiv 6\equiv -1\quad (\mathrm{mod}\:7)\]
となります。$p=11$ のときは
\[(11-1)\,!=10!=3628800\equiv 10\equiv -1\quad (\mathrm{mod}\:11)\]
このことから、$p$ が素数のときには
\[(p-1)\,!\equiv -1\quad (\mathrm{mod}\:p)\]
が成り立っているのではないかと推測できます。ウィルソンの定理 を証明してみましょう。

[証明] 前回記事より $a^{p-1}$ は
\[a^{p-1}\equiv (a-1)\,(a-2)\,\cdots\,(a-(p-1))\quad (\mathrm{mod}\:p)\]
と因数分解できます。両辺の定数項を比較すると
\[-1\equiv (-1)^{p-1}(p-1)\,!\quad (\mathrm{mod}\:p)\]
となります。$p-1$ は偶数なので $(-1)^{p-1}$ の符号は正となり
\[(p-1)\,!\equiv -1\quad (\mathrm{mod}\:p)\]
これで $p$ が素数ならば $(p-1)\,!\equiv -1$ であることは示せましたが、$p$ が素数でなくとも成り立つかもしれません。しかし先ほどの定理 F2 により、合成数 $m$ については
\[(m-1)\,!\equiv\begin{cases}2\;(\mathrm{mod}\:m)& (m=4)\\[6pt]
0\;(\mathrm{mod}\:m)& (m\neq 4)\end{cases}\]
となるので、$-1$ と合同にはなりません。したがって、$p$ が素数であるための必要十分条件は
\[(p-1)\,!\equiv -1\quad (\mathrm{mod}\:p)\]
となります。（証明終）

とはいえ、ウィルソンの定理を素数判定に用いるのはのは実用的ではありません。たとえば $431$ が素数であることを確かめようと思ったら $430!$ を計算しなくてはなりませんが、こんな巨大数を計算させると Excel でもオーバーフローしてしまいます。