リュカ–レーマー・テストの証明
ω 2 p ≡ 1 ( mod F ) {\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}}
より、2 は e の倍数。2 > e ならば、e = 2 (tは0以上p−1以下の整数)となる。言い換えれば 2 は e の倍数となる。つまり、
ω 2 p − 1 ≡ 1 ( mod F ) {\displaystyle \omega ^{2^{p-1}}\equiv {1}{\pmod {F}}}
となるはずである。しかし、上の式、
ω 2 p − 1 + 1 = k F ω 2 p − 2 {\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}}
より、
ω 2 p − 1 ≡ − 1 ( mod F ) {\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {F}}}
よって、2 = e となる。しかし、F は Q の一番小さい素因数なので、
F ≦ Q < 2 p 2 . {\displaystyle F\leqq {\sqrt {Q}}<2^{\frac {p}{2}}.}
よって、F − 1 < 2 となる。 よって、2 = e なので、F − 1 < e となり 1 ≤ e ≤ F − 1 と矛盾する。 よって、背理法により、Sp−2 ≡ 0 (mod Q) ということは、Q は素数であるということの十分条件である。