ミラー–ラビン素数判定法
が成立する。
これらのいずれかが真となることを示すため、以下のフェルマーの小定理を利用する:
a n − 1 ≡ 1 ( mod n ) {\displaystyle a^{n-1}\equiv 1{\pmod {n}}}
ここで、
a n − 1 = a 2 s ⋅ d ≡ 1 ( mod n ) {\displaystyle a^{n-1}=a^{2^{s}\cdot d}\equiv 1{\pmod {n}}}
であるから、この平方根は上述の補題から 1 または −1 (mod n)である。−1 の場合は後者の合同式が成り立つ。
1 の場合はさらに平方根を考えていくと、上述の補題から 1 または −1 (mod n)となる。一度も −1 (mod n)とならないまま、r = 0 となったとする。
a 2 0 ⋅ d = a d ≢ 1 ( mod n ) {\displaystyle a^{2^{0}\cdot d}=a^{d}\not \equiv 1{\pmod {n}}}
この場合後者の合同式は成立せず、前者の合同式が成立する。
ミラー–ラビン素数判定法は上記の主張の対偶に基づいている。すなわち、整数 n に対し、以下が成り立つ a を見つけたとする。
a d ≢ 1 ( mod n ) {\displaystyle a^{d}\not \equiv 1{\pmod {n}}}