ウィルソンの定理
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 = a とおくと、b ≡ 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) となるから矛盾する。(証明終)