actions

ウィルソンの定理

ウィルソンの定理(ウィルソンのていり)は初等整数論における素数に関する次のような定理である。

テンプレート:Math theorem

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

歴史

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

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

剰余表
[math]n[/math] [math](n-1)![/math] [math](n-1)! \; \bmod \; n[/math]
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 が存在する。このとき、フェルマーの小定理より、

[math]a^{p-1} \equiv 1 \pmod{p}.[/math]

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

[math]a^1 a^2 \dotsm a^{p-1} \equiv (p-1)! \pmod{p}[/math]

となる。一方、

[math]a^1 a^2 \dotsm a^{p-1} = a^{1+2+\dotsb+(p-1)} = a^{p(p-1)/2}[/math]

が成り立つ。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) となるから矛盾する。(証明終

脚注

参考文献

関連項目

外部リンク