リュカ–レーマー・テストの証明
次に p が奇素数であり、かつ Q が素数であれば、Sp−2 ≡ 0 (mod Q) であることを証明する。 この証明をするうえで、平方剰余の相互法則を使う。 まず、二項定理より、
( 1 + 3 ) Q = 1 + ( Q 1 ) ( 3 ) + ( Q 2 ) ( 3 ) 2 + . . . + ( Q Q − 1 ) ( 3 ) Q − 1 + ( 3 ) Q {\displaystyle (1+{\sqrt {3}})^{Q}=1+{\begin{pmatrix}Q\\1\end{pmatrix}}({\sqrt {3}})+{\begin{pmatrix}Q\\2\end{pmatrix}}({\sqrt {3}})^{2}+...+{\begin{pmatrix}Q\\Q-1\end{pmatrix}}({\sqrt {3}})^{Q-1}+({\sqrt {3}})^{Q}}
Q は素数なので ( Q n ) = Q ! n ! ( Q − n ) ! {\displaystyle {\begin{pmatrix}Q\\n\end{pmatrix}}={\frac {Q!}{n!(Q-n)!}}} は n = 0, Q の場合を除いて Q の倍数。よって、
p が奇素数のとき、メルセンヌ数 Mp = 2 − 1 が素数となるための必要十分条件は、S0 = 4, Sn = Sn−1 − 2 (n ≧ 1) と定義したときに Sp−2 が Mp で割り切れることである。
これの一般化であるリュカ–レーマー–リーゼル・テストもある。
なおフェルマー数にも同様な素数判定の定理であるペピンの判定法(英語版)がある。
まず、Sp−2 ≡ 0 (mod Q) であれば、Q が素数であることを証明する。 Sp−2 ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、Sp−2 は Q の一番小さい素因数 F を用いて Sp−2 = kF(kは自然数)と表せる。Sn の一般項から
ω 2 p − 2 + ω ̄ 2 p − 2 = k F {\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kF}
となる。 ω ω ̄ = 1 {\displaystyle \omega {\bar {\omega }}=1} なので、両辺に ω 2 p − 2 {\displaystyle \omega ^{2^{p-2}}} をかけて、
ω 2 p − 1 + 1 = k F ω 2 p − 2 {\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}}
1を移項し、両辺を2乗すると、
ω 2 p = k 2 F 2 ω 2 p − 1 − 2 k F ω 2 p − 2 + 1. {\displaystyle \omega ^{2^{p}}=k^{2}F^{2}\omega ^{2^{p-1}}-2kF\omega ^{2^{p-2}}+1.}
よって、
ω 2 p ≡ 1 ( mod F ) {\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}}