ウィルソンの定理
ウィルソンの定理（ウィルソンのていり）は初等整数論における素数に関する次のような定理である。
p が大きくなるにつれて計算量が膨大になるため、素数かどうかを判定するために用いるには実用的ではない。
歴史
この定理は、10世紀のペルシャの数学者イブン・アル・ハイサム（アルハゼン）によって最初に発見された[1]。しかし、ヨーロッパでは長いこと知られず、イギリスのエドワード・ウェアリングの弟子だったジョン・ウィルソンによって発見され、1770年にウェアリングによって公表され、「ウィルソンの定理」の名がついた[2][3]。しかしウェアリングもウィルソンもこの定理の証明はできず、1773年にラグランジュが最初の証明をした[2]。なお、ゴットフリート・ライプニッツがその一世紀前に結果に気がついていたという証拠があるが、ライプニッツはそれを公表しなかった[2]。
例
n の値が 2 から 30 までの階乗と剰余の例をあげる。m を n で割った剰余を 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) となるから矛盾する。（証明終）
脚注
参考文献
- 高木貞治 『初等整数論講義』 共立出版、1971年10月、第2版、67頁、70-71頁。ISBN 4-320-01001-9。
- Hardy, G. H.; Wright, E. M. (31 July 2008), Heath-Brown, Roger; Silverman, Joseph; Wiles, Andrew, eds., An Introduction to the Theory of Numbers (sixth ed.), USA: Oxford University Press, ISBN 978-0-19-921986-5
- G.H.ハーディ・E.M.ライト 『数論入門』I、示野信一・矢神毅翻訳、シュプリンガー・フェアラーク東京、2001年7月、89-90頁、114-116頁、137頁。ISBN 4-431-70848-0。 - 原書第5版（1979年）の邦訳。
- G・H・ハーディ・E・M・ライト 『数論入門』I、示野信一・矢神毅翻訳、丸善出版、2012年1月、89-90頁、114-116頁、137頁。ISBN 978-4-621-06226-5。 - ハーディ＆ライト(2001)の復刊。
関連項目
外部リンク
- Weisstein, Eric W. “Wilson's Theorem”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。