ウィルソンの定理とは？具体例、証明を紹介

どうも、木村（@kimu3_slime）です。

今回は、整数の性質に関するウィルソンの定理を、具体例を通して紹介します。

ウィルソンの定理とは
ウィルソンの定理の証明
こちらもおすすめ

ウィルソンの定理とは

ウィルソンの定理（Wilson’s theorem）とは、素数に関する次の主張です。

\(p\)を素数とする。このとき、\((p-1)! \equiv -1 \,(\mathrm{mod}\, p)\)が成り立つ。

これは逆も成り立つ。2以上の整数\(n\)が\((n-1)! \equiv -1 \,(\mathrm{mod}\, n)\)を満たすならば、\(n\)は素数である。

ここで\(n! := 1\cdot 2\cdot \cdots n\)は、\(n\)の階乗と呼ばれるものです。合同式\(\equiv\)については、「倍数同士の和は同じ倍数となること、整数の合同modとは」を参照してください。

合同式\((n-1)! \equiv -1 \,(\mathrm{mod}\, n)\)は、\((n-1)! \equiv n-1 \,(\mathrm{mod}\, n)\)や、\((n-1)! +1 \)が\(n\)で割り切れる、と言っても同じですね。

さて、ウィルソンの定理が何を言っているのか、具体例を通じて考えてみましょう。

\(p=2\)のとき、\(1 \equiv -1 \,(\mathrm{mod}\, 2)\)は、合同式の定義より成り立つ簡単な式です。

\(p=3\)のとき、\(2 \equiv -1 \,(\mathrm{mod}\, 3)\)も確かに成り立ちます。なんだか当たり前ですね。

\(n=4\)のとき、\((4-1)! \equiv 6 \equiv 2\,(\mathrm{mod}\, 4) \)で、ウィルソンの定理の逆の対偶、合成数ならば\((n-1)! \not \equiv -1 \,(\mathrm{mod}\, n)\)が成り立っています。

\(p=5\)のとき、\(4! =1\cdot 2\cdot 3\cdot 4\)です。\(2\cdot 3 \equiv 1 \,(\mathrm{mod}\, 5)\)で、\( 4\equiv -1 \,(\mathrm{mod}\, 5)\)なので、\(4! \equiv -1 \,(\mathrm{mod}\, 5)\)が言えました。

そろそろ、一般的な調べ方がわかってくるような気がします。

\(n=6\)のとき、\(5! =1\cdot 2\cdot 3\cdot 4\cdot 5\)です。\(6\)は素数でなく、\(2\cdot 3\)が登場しているので、\(5! \equiv 0\,(\mathrm{mod}\, 6) \)ですね。

\(p=7\)のとき。当然\(p-1 \equiv -1 \,(\mathrm{mod}\, p)\)です。残りの\(2,3,4,5\)の積が\(p\)を法として\(1\)となるかを調べれば良いことになります。\(2\cdot 4 \equiv 1 \,(\mathrm{mod}\, 7)\)、\(3\cdot 5 \equiv 1\,(\mathrm{mod}\, 7)\)なので、\(6! \equiv -1\,(\mathrm{mod}\, 7)\)が言えました。ペアで\(1\)になる数を探せば良さそうです。

ウィルソンの定理の証明

では、ウィルソンの定理を一般的に証明してみましょう。

まず、\(p\)を素数として、\((p-1)! \equiv -1 \,(\mathrm{mod}\, p)\)が成り立つことを示します。

まず、\(p-1 \equiv -1 \,(\mathrm{mod}\, p)\)です。残りの\(2,3,\cdots,p-2\)の積が、\(p\)を法として1に等しいことを示しましょう。

\(p=2,3\)のとき成り立つことは既に示したので、\(p > 3\)とします。このとき素数\(p\)は奇数であり、\(2,3,\cdots,p-2\)は偶数個となります。

線形合同式\(ax \equiv 1 \,(\mathrm{mod}\, p)\)は、\(a,p\)が互いに素のとき、\(p\)を法として一意な解を持つことが知られています。\(a=2,3,\cdots,p-2\)とすると、\(p\)は素数であり\(a,p\)は互いに素なので、\(ax \equiv 1 \,(\mathrm{mod}\, p)\)を満たす\(x\)が一意に存在します。

このとき、\(a\not \equiv x\,(\mathrm{mod}\, p)\)です。仮に\(a\equiv x\,(\mathrm{mod}\, p)\)とすると、\((a-1)(a+1) \equiv 0\,(\mathrm{mod}\, p)\)なので、\((a-1) \equiv 0\,(\mathrm{mod}\, p)\)または\((a+1) \equiv 0\,(\mathrm{mod}\, p)\)です。これは\(a=2,3,\cdots,p-2\)と矛盾します。

よって、\(a=2,3,\cdots,p-2\)は、\(ax \equiv 1 \,(\mathrm{mod}\, p)\)、\(a\not \equiv x\,(\mathrm{mod}\, p)\)を満たす\(\frac{p-3}{2}\)個の組に分かれます。その積を取った合同式も成り立つので、\((p-2)! =2\cdot 3\cdot \cdots p-2 \equiv 1\,(\mathrm{mod}\, p)\)です。これと\(p-1 \equiv -1 \,(\mathrm{mod}\, p)\)の積を取ることで、\((p-1)! \equiv -1 \,(\mathrm{mod}\, p)\)が得られました。

ウィルソンの定理の逆、2以上の整数\(n\)が\((n-1)! \equiv -1 \,(\mathrm{mod}\, n)\)を満たすならば、\(n\)は素数であることを示しましょう。

その対偶、\(n\)が合成数ならば、\((n-1)! \not \equiv -1 \,(\mathrm{mod}\, n)\)を満たすことを示しましょう。

\(n=4\)のときは示したので、\(n>4\)の合成数を考えます。\(n\)が合成数であることから、\(n=dk\)、\(2\leq d,k \leq n-1\)を満たす整数\(d,k\)が存在します。

\(d \neq k\)のとき、\((n-1)!\)の因数には\(d,k\)が含まれるので、\(d \mid (n-1)!,k \mid (n-1)!\)であり、したがって\(n \mid (n-1)!\)で、\((n-1)! \equiv 0 \,(\mathrm{mod}\, n)\)が言えました。

一方で、\(d = k\)のときを考えます。\((n-1)!\)の因数には\(d\)が含まれるので、\(d \mid (n-1)!\)です。さらに、\(2d\)を考えると、\(2d \leq n-1\)です（一般に\(n \geq 9\)のとき、\(4n \leq (n-1)^2\)が成り立ち、その平方根を取れば言える。\(n>4\)の平方数を考えているので、\(n\geq 9\)であり、仮定は満たされています）。よって\(2d\)は\(\frac{(n-1)!}{d}\)の因数として含まれ、\(2d \mid\frac{(n-1)!}{d}\)です。つまり、\(\frac{(n-1)!}{d} =2dk\)を満たす整数\(k\)が存在し、整理すれば\((n-1)! =2d^2k=2kn\)で、\((n-1)! \equiv 0 \,(\mathrm{mod}\, n)\)が言えました。

ウィルソンの定理は、フェルマーの小定理と同様の一般化（ガウスによる一般化）が知られています。階乗ではなく、互いに素な数だけの積を考える形になります。

フェルマーの小定理は素数の判定法として使われていますが、ウィルソンの定理も活用できないのでしょうか。素数であることの必要十分条件としては、使いやすそうです。しかしながら、階乗\((n-1)!\)は非常に大きな数になって扱いきれないので、現実的ではないようです。理論的に判定可能であることと、コンピュータで現実的な時間で判定可能なことには、違いがありますね。

また、ウィルソンの定理は平方剰余の性質を示すためにも応用されます。これについては別の記事にて。

以上、ウィルソンの定理の具体例とその証明を紹介しました。

階乗\((n-1)!\)には確かにいろいろな数が含まれていますが、それを\(n\)で割ったあまりを調べることで、\(n\)が素数かそうでないかがわかるのは面白いですね。

木村すらいむ（@kimu3_slime）でした。ではでは。