原始根を用いた証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/25 13:55 UTC 版)
「ウィルソンの定理」の記事における「原始根を用いた証明」の解説
p = 2 の場合は明らかに成り立つので、以下 p は奇素数とする。p は素数だから法 p に関する原始根 a が存在する。このとき、フェルマーの小定理より、 a p − 1 ≡ 1 ( mod p ) . {\displaystyle a^{p-1}\equiv 1{\pmod {p}}.} aは原始根だから、a1, a2, ..., ap−1(≡1) はそれぞれ p を法として還元すると、1, 2, ..., p − 1 の並べ替えである。よって、 a 1 a 2 ⋯ a p − 1 ≡ ( p − 1 ) ! ( mod p ) {\displaystyle a^{1}a^{2}\dotsm a^{p-1}\equiv (p-1)!{\pmod {p}}} となる。一方、 a 1 a 2 ⋯ a p − 1 = a 1 + 2 + ⋯ + ( p − 1 ) = a p ( p − 1 ) / 2 {\displaystyle a^{1}a^{2}\dotsm a^{p-1}=a^{1+2+\dotsb +(p-1)}=a^{p(p-1)/2}} が成り立つ。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) となるから矛盾する。（証明終）
※この「原始根を用いた証明」の解説は、「ウィルソンの定理」の解説の一部です。
「原始根を用いた証明」を含む「ウィルソンの定理」の記事については、「ウィルソンの定理」の概要を参照ください。
- 原始根を用いた証明のページへのリンク
