ウィルソンの定理

 今回は正整数が素数であるための条件である ウィルソンの定理 を証明しますが、その前に少し準備をします。$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\]
となりますが、因子の1つが $6=2\cdot 3$ なので、$(9-1)\,!$ の中に $3$ が2つ含まれていることになり、$(9-1)\,!$ は $9$ で割り切れます:
 
\[(9-1)\,!\equiv 0\quad (\mathrm{mod}\:9)\]
 これは $9-1\geq 2\cdot 3$ であるから割り切れたのです。そんなことは、ほとんど自明であるように思えますが、こうならない例が1つだけあるのです。それは $m=4=2^2$ のときで、
 
\[(4-1)\,!=3\cdot 2\cdot 1\]
ですから、$4-1\lt 2\cdot 2$ であるために、$(4-1)\,!$ の中に $2$ という因子は1つしか含まれておらず、$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$ で割り切れることになります。
 以上をまとめると、

[定理 F2] $m$ を合成数とすると
\[(m-1)\,!\equiv\begin{cases}2\;(\mathrm{mod}\:m)& (m=4)\\[6pt]
0\;(\mathrm{mod}\:m)& (m\neq 4)\end{cases}\]

 

ウィルソンの定理

 本題はここからです。$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)\]
が成り立っているのではないかと推測できます。ウィルソンの定理 を証明してみましょう。

[定理 F3 ウィルソンの定理] 正整数 $p$ が素数であるための必要十分条件は
\[(p-1)\,!\equiv -1\quad (\mathrm{mod}\:p)\]

[定理 F3 の証明] 前回記事 より $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 でもオーバーフローしてしまいます。

 ≫ 2 項合同方程式 ≫ 整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。