Fermat's little theorem
が成り立つ。"b" = "a""p"("p"−1)/2 とおくと、"b"2 ≡ 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" が奇数であることに反する。