ウィルソンの定理

ウィルソンの定理（ウィルソンのていり、英: Wilson's theorem）は初等整数論における素数に関する次のような定理である。

ウィルソンの定理 ― p が素数ならば (p − 1)! ≡ −1 (mod p) が成り立つ。
逆に、整数 p > 1 に対し、(p − 1)! ≡ −1 (mod p) ならば、p は素数である。

p が大きくなるにつれて計算量が膨大になるため、素数かどうかを判定するために用いるには実用的ではない。

歴史

この定理は、10世紀のペルシャの数学者イブン・アル・ハイサム（アルハゼン）によって最初に発見された^[1]。しかし、ヨーロッパでは長いこと知られず、イギリスのエドワード・ウェアリングの弟子だったジョン・ウィルソンによって発見され、1770年にウェアリングによって公表され、「ウィルソンの定理」の名がついた^[2][3]。しかしウェアリングもウィルソンもこの定理の証明はできず、1773年にラグランジュが最初の証明をした^[2]。なお、ゴットフリート・ライプニッツがその一世紀前に結果に気がついていたという証拠があるが、ライプニッツはそれを公表しなかった^[2]。

例

n の値が 2 から 30 までの階乗と剰余の例をあげる。m を n で割った剰余を m mod n と表記する。n が素数の場合は背景色をピンクに、n が合成数の場合は背景色をグリーンにして表示する。

剰余表

${\displaystyle n}$	${\displaystyle (n-1)!}$	${\displaystyle (n-1)!\;{\bmod {\;}}n}$
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

証明

原始根を用いた証明

p = 2 の場合は明らかに成り立つので、以下 p は奇素数とする。p は素数だから法 p に関する原始根 a が存在する。このとき、フェルマーの小定理より、

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

aは原始根だから、a¹, a², ..., a^p−1(≡1) はそれぞれ p を法として還元すると、1, 2, ..., p − 1 の並べ替えである。よって、

${\displaystyle a^{1}a^{2}\dotsm a^{p-1}\equiv (p-1)!{\pmod {p}}}$

となる。一方、

${\displaystyle a^{1}a^{2}\dotsm a^{p-1}=a^{1+2+\dotsb +(p-1)}=a^{p(p-1)/2}}$

が成り立つ。b = a^p(p−1)/2 とおくと、b² ≡ 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) となるから矛盾する。（証明終）