リュカ–レーマー・テストの証明
{\displaystyle \omega ^{2^{p-1}}{\bar {\omega }}^{2^{p-2}}=(\omega ^{2^{p-2}})^{2}({\bar {\omega }}^{2^{p-2}})=\omega ^{2^{p-2}}\equiv {-{\bar {\omega }}^{2^{p-2}}}{\pmod {Q}}.}
両辺に ω ̄ 2 p − 2 {\displaystyle {\bar {\omega }}^{2^{p-2}}} を足して、
ω 2 p − 2 + ω ̄ 2 p − 2 = S p − 2 ≡ 0 ( mod Q ) . {\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=S_{p-2}\equiv {0}{\pmod {Q}}.}
よって、Sp−2 ≡ 0 (mod Q) であることは、Q が素数であることの必要条件である。
以上により、リュカ-レーマー・テスト
S p − 2 ≡ 0 ( mod Q ) ⟺ ∀ u ∈ N [ 2 ≦ u < Q → Q ≢ 0 ( mod u ) ] {\displaystyle S_{p-2}\equiv {0}{\pmod {Q}}\Longleftrightarrow \forall {u}\in \mathbb {N} [2\leqq {u}<Q\to {Q}\not \equiv {0}{\pmod {u}}]}
が示された。Q.E.D.