リュカ–レーマー・テストの証明
( 1 + 3 ) Q ≡ 1 + ( 3 ) Q ( mod Q ) = 1 + 3 Q − 1 2 ( 3 ) {\displaystyle {\begin{aligned}(1+{\sqrt {3}})^{Q}&\equiv 1+({\sqrt {3}})^{Q}{\pmod {Q}}\\&=1+3^{\frac {Q-1}{2}}({\sqrt {3}})\\\end{aligned}}}
Q ≡ −1 (mod 4), 3 ≡ −1 (mod 4) で、平方剰余の相互法則により、
( Q 3 ) ( 3 Q ) = − 1 {\displaystyle \left({\frac {Q}{3}}\right)\left({\frac {3}{Q}}\right)={-1}}
Q = 2 − 1 = 2(2 − 1) + 1 = 2((3 + 1) − 1) + 1 ≡ 1 (mod 3)よって
( 3 Q ) = − 1 , ( Q 3 ) = 1. {\displaystyle \left({\frac {3}{Q}}\right)={-1},\left({\frac {Q}{3}}\right)=1.}
つまり、
3 Q − 1 2 ≡ − 1 ( mod Q ) {\displaystyle 3^{\frac {Q-1}{2}}\equiv {-1}{\pmod {Q}}}
が成り立ち、よって、
( 1 + 3 ) Q ≡ 1 + ( − 1 ) 3 ( mod Q ) . {\displaystyle (1+{\sqrt {3}})^{Q}\equiv {1+(-1){\sqrt {3}}}{\pmod {Q}}.