リュカ–レーマー・テストの証明
平方剰余の相互法則の第2補充法則 ( 2 Q ) = ( − 1 ) Q 2 − 1 8 = 1 {\displaystyle \left({\frac {2}{Q}}\right)=(-1)^{\frac {Q^{2}-1}{8}}={1}} により、
2 Q − 1 2 ≡ 1 ( mod Q ) . {\displaystyle 2^{\frac {Q-1}{2}}\equiv {1}{\pmod {Q}}.}
よって、
ω Q + 1 2 ≡ − 1 ( mod Q ) . {\displaystyle \omega ^{\frac {Q+1}{2}}\equiv {-1}{\pmod {Q}}.}
ここで、 Q + 1 2 = 2 p − 1 {\displaystyle {\frac {Q+1}{2}}=2^{p-1}} なので、
ω 2 p − 1 ≡ − 1 ( mod Q ) {\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {Q}}}
となる。両辺に ω ̄ 2 p − 2 {\displaystyle {\bar {\omega }}^{2^{p-2}}} を掛けて、
ω 2 p − 1 ω ̄ 2 p − 2 = ( ω 2 p − 2 ) 2 ( ω ̄ 2 p − 2 ) = ω 2 p − 2 ≡ − ω ̄ 2 p − 2 ( mod Q ) .