ウィルソンの定理

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

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

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

 例 
n の値が 2 から 30 までの階乗と剰余の例をあげる。m を n で割った剰余を m mod n と表記する。n が素数の場合は背景色をピンクに、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 が存在する。このとき、フェルマーの小定理より、

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

となる。一方、

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

 脚注 

 参考文献 

 - 原書第5版（1979年）の邦訳。
 - ハーディ＆ライト(2001)の復刊。

 関連項目 

ウィルソン商
合同式
指数 (初等整数論)
素数
フェルマーの小定理

 外部リンク 

Category:合同算術
Category:数論の定理
Category:数学に関する記事
Category:数学のエポニム