ウィルソンの定理(ウィルソンのていり、英: Wilson's theorem)は初等整数論における素数に関する次のような定理である。
ウィルソンの定理 ― p が素数ならば (p − 1)! ≡ −1 (mod p) が成り立つ。
逆に、整数 p > 1 に対し、(p − 1)! ≡ −1 (mod p) ならば、p は素数である。
p が大きくなるにつれて計算量が膨大になるため、素数かどうかを判定するために用いるには実用的ではない。 この定理は、10世紀のペルシャの数学者イブン・アル・ハイサム(アルハゼン)によって最初に発見された[1]。しかし、ヨーロッパでは長いこと知られず、イギリスのエドワード・ウェアリングの弟子だったジョン・ウィルソン n の値が 2 から 30 までの階乗と剰余の例をあげる。m を n で割った剰余を m mod n と表記する。n が素数の場合は背景色をピンクに、n が合成数の場合は背景色をグリーンにして表示する。 剰余表 n {\displaystyle n} ( n − 1 ) ! {\displaystyle (n-1)!} ( n − 1 ) ! mod n {\displaystyle (n-1)!\;{\bmod {\;}}n} p = 2 の場合は明らかに成り立つので、以下 p は奇素数とする。p は素数だから法 p に関する原始根 a が存在する。このとき、フェルマーの小定理より、 a p − 1 ≡ 1 ( mod p ) . {\displaystyle a^{p-1}\equiv 1{\pmod {p}}.} aは原始根だから、a1, a2, ..., ap−1(≡1) はそれぞれ p を法として還元すると、1, 2, ..., p − 1 の並べ替えである。よって、 a 1 a 2 ⋯ a p − 1 ≡ ( p − 1 ) ! ( mod p ) {\displaystyle a^{1}a^{2}\dotsm a^{p-1}\equiv (p-1)!{\pmod {p}}} となる。一方、 a 1 a 2 ⋯ a p − 1 = a 1 + 2 + ⋯ + ( p − 1 ) = a p ( p − 1 ) / 2 {\displaystyle a^{1}a^{2}\dotsm a^{p-1}=a^{1+2+\dotsb +(p-1)}=a^{p(p-1)/2}} が成り立つ。b = ap(p−1)/2 とおくと、b2 ≡ 1 (mod p) だから b ≡ ±1 (mod p) である。示したいのは b ≡ −1 (mod p) なので b ≡ 1 (mod p) と仮定して矛盾を導く。a は原始根だから、フェルマーの小定理より、p(p − 1)/2 は p − 1 で割り切れる。ゆえに p/2 は整数となるが、これは p が奇数であることに反する。 逆に、n > 1 を合成数とすると、n はある素数 2 ≤ q < n で割り切れるので、(n − 1)! ≡ 0 (mod q) である。もし (n − 1)! ≡ −1 (mod n) とすると、(n − 1)! ≡ −1 (mod q) となるから矛盾する。(証明終)
歴史
例
211
322
462
5244
61200
77206
850400
9403200
103628800
11362880010
12399168000
1347900160012
1462270208000
15871782912000
1613076743680000
172092278988800016
183556874280960000
19640237370572800018
201216451004088320000
2124329020081766400000
22510909421717094400000
23112400072777760768000022
24258520167388849766400000
256204484017332394393600000
26155112100433309859840000000
274032914611266056355840000000
28108888694504183521607680000000
2930488834461171386050150400000028
3088417619937397019545436160000000
証明
原始根を用いた証明
脚注[脚注の使い方]^ O'Connor, John J.; Robertson, Edmund F., “Abu Ali al-Hasan ibn al-Haytham”
^ a b c O'Connor, John J.; Robertson, Edmund F., “John Wilson”