ウィルソンの定理のソースを表示

'''ウィルソンの定理'''（ウィルソンのていり、{{Lang-en-short|Wilson's theorem}}）は[[初等整数論]]における[[素数]]に関する次のような[[定理]]である。

{{math_theorem|name=ウィルソンの定理|''p'' が[[素数]]ならば (''p'' &minus; 1)! ≡ &minus;1 (mod ''p'') が成り立つ。<br />逆に、整数 ''p'' > 1 に対し、(''p'' &minus; 1)! ≡ &minus;1 (mod ''p'') ならば、''p'' は素数である。}}

''p'' が大きくなるにつれて[[計算複雑性理論|計算量]]が膨大になるため、素数かどうかを判定するために用いるには実用的ではない。

== 歴史 ==
この定理は、[[10世紀]]の[[ペルシャ]]の数学者[[イブン・アル・ハイサム]]（アルハゼン）によって最初に発見された<ref name="Al-Haytham">{{MacTutor|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham}}</ref>。しかし、[[ヨーロッパ]]では長いこと知られず、[[イギリス]]の[[エドワード・ウェアリング]]の弟子だった[[ジョン・ウィルソン (数学)|ジョン・ウィルソン]]によって発見され、[[1770年]]にウェアリングによって公表され、「ウィルソンの定理」の名がついた<ref name="Wilson_John">{{MacTutor|id=Wilson_John|title=John Wilson}}</ref><ref>[[#WilsonsTheorem|WilsonsTheorem]]</ref>。しかしウェアリングもウィルソンもこの定理の[[証明 (数学)|証明]]はできず、[[1773年]]に[[ジョゼフ＝ルイ・ラグランジュ|ラグランジュ]]が最初の証明をした<ref name="Wilson_John" />。なお、[[ゴットフリート・ライプニッツ]]がその一世紀前に結果に気がついていたという証拠があるが、ライプニッツはそれを公表しなかった<ref name="Wilson_John" />。

== 例 ==
''n'' の値が 2 から 30 までの階乗と剰余の例をあげる。''m'' を ''n'' で割った剰余を ''m'' mod ''n'' と表記する。''n'' が素数の場合は背景色を<span style="background-color:#FFC0CB">ピンク</span>に、''n'' が合成数の場合は背景色を<span style="background-color:#98FB98">グリーン</span>にして表示する。
{| class="wikitable" style="text-align:right"
|+ 剰余表
! <math>n</math> !! <math>(n-1)!</math> !! <math>(n-1)! \; \bmod \; n</math>
|- style="background-color:#FFC0CB"
| 2 || 1 || 1
|- style="background-color:#FFC0CB"
| 3 || 2 || 2
|- style="background-color:#98FB98"
| 4 || 6 || 2
|- style="background-color:#FFC0CB"
| 5 || 24 || 4
|- style="background-color:#98FB98"
| 6 || 120 || 0
|- style="background-color:#FFC0CB"
| 7 || 720 || 6
|- style="background-color:#98FB98"
| 8 || 5040 || 0
|- style="background-color:#98FB98"
| 9 || 40320 || 0
|- style="background-color:#98FB98"
| 10 || 362880 || 0
|- style="background-color:#FFC0CB"
| 11 || 3628800 || 10
|- style="background-color:#98FB98"
| 12 || 39916800 || 0
|- style="background-color:#FFC0CB"
| 13 || 479001600 || 12
|- style="background-color:#98FB98"
| 14 || 6227020800 || 0
|- style="background-color:#98FB98"
| 15 || 87178291200 || 0
|- style="background-color:#98FB98"
| 16 || 1307674368000 || 0
|- style="background-color:#FFC0CB"
| 17 || 20922789888000 || 16
|- style="background-color:#98FB98"
| 18 || 355687428096000 || 0
|- style="background-color:#FFC0CB"
| 19 || 6402373705728000 || 18
|- style="background-color:#98FB98"
| 20 || 121645100408832000 || 0
|- style="background-color:#98FB98"
| 21 || 2432902008176640000 || 0
|- style="background-color:#98FB98"
| 22 || 51090942171709440000 || 0
|- style="background-color:#FFC0CB"
| 23 || 1124000727777607680000 || 22
|- style="background-color:#98FB98"
| 24 || 25852016738884976640000 || 0
|- style="background-color:#98FB98"
| 25 || 620448401733239439360000 || 0
|- style="background-color:#98FB98"
| 26 || 15511210043330985984000000 || 0
|- style="background-color:#98FB98"
| 27 || 403291461126605635584000000 || 0
|- style="background-color:#98FB98"
| 28 || 10888869450418352160768000000 || 0
|- style="background-color:#FFC0CB"
| 29 || 304888344611713860501504000000 || 28
|- style="background-color:#98FB98"
| 30 || 8841761993739701954543616000000 || 0
|}

== 証明 ==
=== 原始根を用いた証明 ===
''p'' = 2 の場合は明らかに成り立つので、以下 ''p'' は奇素数とする。''p'' は素数だから法 ''p'' に関する[[原始根]] ''a'' が存在する。このとき、[[フェルマーの小定理]]より、
:<math>a^{p-1} \equiv 1 \pmod{p}.</math>
''a''は原始根だから、''a''<sup>1</sup>, ''a''<sup>2</sup>, ..., ''a''<sup>''p''&minus;1</sup>(≡1) はそれぞれ ''p'' を法として還元すると、1, 2, ..., ''p'' &minus; 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'' = ''a''<sup>''p''(''p''&minus;1)/2</sup> とおくと、''b''<sup>2</sup> &equiv; 1 (mod ''p'') だから ''b'' &equiv; ±1 (mod ''p'') である。示したいのは ''b'' &equiv; &minus;1 (mod ''p'') なので ''b'' &equiv; 1 (mod ''p'') と仮定して矛盾を導く。''a'' は原始根だから、フェルマーの小定理より、''p''(''p'' &minus; 1)/2 は ''p'' &minus; 1 で割り切れる。ゆえに ''p''/2 は整数となるが、これは ''p'' が奇数であることに反する。

逆に、''n'' > 1 を合成数とすると、''n'' はある素数 2 &le; ''q'' &lt; ''n'' で割り切れるので、(''n'' &minus; 1)! ≡ 0 (mod ''q'') である。もし (''n'' &minus; 1)! ≡ &minus;1 (mod ''n'') とすると、(''n'' &minus; 1)! ≡ &minus;1 (mod ''q'') となるから矛盾する。（[[Q.E.D.|証明終]]）

== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}

== 参考文献 ==
*{{Cite book|和書|author=高木貞治|authorlink=高木貞治|year=1971|month=10|title=初等整数論講義|edition=第2版|publisher=[[共立出版]]|isbn=4-320-01001-9|url=http://www.kyoritsu-pub.co.jp/bookdetail/9784320010017|pages=67,70-71|ref=高木1971}}
*{{Citation |last1=Hardy |first1=G. H. |author1-link=ゴッドフレイ・ハロルド・ハーディ |last2=Wright |first2=E. M. |author2-link=エドワード・メイトランド・ライト |editor1-last=Heath-Brown |editor1-first=Roger |editor1-link=ロジャー・ヒース＝ブラウン |editor2-last=Silverman |editor2-first=Joseph |editor2-link=ジョセフ・シルヴァーマン |editor3-last=Wiles |editor3-first=Andrew |editor3-link=アンドリュー・ワイルズ |year=2008 |date=31 July 2008 |title=An Introduction to the Theory of Numbers |edition=sixth |place=USA |publisher=Oxford University Press |isbn=978-0-19-921986-5 |url=http://ukcatalogue.oup.com/product/9780199219865.do#.UdgOFeaCjIU }}
**{{Cite book|和書|author=G.H.ハーディ|authorlink=ゴッドフレイ・ハロルド・ハーディ|coauthors={{仮リンク|エドワード・メイトランド・ライト|label=E.M.ライト|en|E. M. Wright}}|others=[[示野信一]]・[[矢神毅]]翻訳|year=2001|month=7|title=数論入門|volume=I|publisher=[[シュプリンガー・フェアラーク東京]]|isbn=4-431-70848-0|pages=89-90,114-116,137|ref=ハーディ＆ライト2001}} - 原書第5版（1979年）の邦訳。
**{{Cite book|和書|author=G・H・ハーディ|coauthors=E・M・ライト|others=示野信一・矢神毅翻訳|year=2012|month=1|title=数論入門|volume=I|publisher=[[丸善出版]]|isbn=978-4-621-06226-5|url=http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062265.html|pages=89-90,114-116,137|ref=ハーディ＆ライト2012}} - [[#ハーディ＆ライト2001|ハーディ＆ライト(2001)]]の復刊。

== 関連項目 ==
{{Div col}}
*[[ウィルソン商]]
*[[合同式]]
*[[指数 (初等整数論)]]
*[[素数]]
*[[フェルマーの小定理]]
{{Div col end}}

== 外部リンク ==
*{{Kotobank|ウィルソンの定理|2=法則の辞典}}
*{{高校数学の美しい物語|744|ウィルソンの定理とその２通りの証明}}
*{{Anchors|WilsonsTheorem}}{{MathWorld|title=Wilson's Theorem|urlname=WilsonsTheorem}}

{{DEFAULTSORT:ういるそんのていり}}
[[Category:合同算術]]
[[Category:数論の定理]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]