Lucas–Lehmerの判定法

$k$ についての数学的帰納法で示す。$k=0$ では $\omega+\bar\omega=4=s_0$ である。$k$ で成り立つとすると、$\omega\bar\omega=1$ から
$$ s_{k+1}=s_k^2-2=\omega^{2^{k+1}}+2(\omega\bar\omega)^{2^k}+\bar\omega^{2^{k+1}}-2=\omega^{2^{k+1}}+\bar\omega^{2^{k+1}} $$
となる。$\square$

$R_q$ は可換環なので二項定理が使え、
$$ (a+b\sqrt3)^q=\sum_{j=0}^{q}\binom qj a^{q-j}(b\sqrt3)^j $$
である。$0< j< q$ では $\binom qj$ は $q$ で割り切れる（二項係数 の命題「素数に関する合同式」）ので、その項は $R_q$ で $0$ になり、$(a+b\sqrt3)^q=a^q+b^q(\sqrt3)^q$ が残る。Fermatの小定理 により整数 $a,b$ について $a^q\equiv a$、$b^q\equiv b\pmod q$ である。また $(\sqrt3)^q=3^{(q-1)/2}\sqrt3$ であり、平方剰余 の定理「Eulerの規準」により $3^{(q-1)/2}\equiv\left(\frac3q\right)\pmod q$ である。これらを合わせて主張を得る。$\square$

1：$p\ge3$ なので $8\mid2^p$ であり、$q\equiv-1\equiv7\pmod8$ である。$2\equiv-1\pmod3$ と $p$ が奇数であることから $2^p\equiv(-1)^p=-1\equiv2\pmod3$ であり、$q\equiv1\pmod3$ である。
2：$q\equiv7\pmod8$ と 平方剰余 の定理「第2補充法則と相互法則」の 1 から $\left(\frac2q\right)=1$ である。$q\equiv1\pmod 3$ より $q\neq3$ であり、$3$ と $q$ は相異なる奇素数である。$q\equiv3\pmod4$ なので、同じ定理の 2（相互法則）により $\left(\frac3q\right)=-\left(\frac q3\right)$ である。$q\equiv1\pmod3$ より $\left(\frac q3\right)=\left(\frac13\right)=1$ なので、$\left(\frac3q\right)=-1$ である。$\square$

$p$ を奇素数とし、$M_p\mid s_{p-2}$ と仮定する。$M_p$ が合成数であったとして矛盾を導く。
$M_p$ の最小の素因数を $q$ とする。$M_p$ は合成数なので $q$ 以上の素因数を重複を込めて 2 つ以上もち、$q^2\le M_p$ である。また $M_p$ は奇数なので $q\ge3$ である。
$R_q$ で考える。$\omega\bar\omega=1$ なので $\omega\in R_q^\times$ である。$q\mid M_p\mid s_{p-2}$ と lem-ll-closed から、$R_q$ において
$$ \omega^{2^{p-2}}+\bar\omega^{2^{p-2}}=0 $$
である。両辺に $\omega^{2^{p-2}}$ を掛け、$(\omega\bar\omega)^{2^{p-2}}=1$ を使うと $\omega^{2^{p-1}}+1=0$、すなわち
$$ \omega^{2^{p-1}}=-1 $$
を得る。両辺を 2 乗して $\omega^{2^p}=1$ である。
$d$ を $R_q^\times$ における $\omega$ の元の位数とする。$\omega^{2^p}=1$ から $d\mid2^p$ なので、$d=2^j$（$0\le j\le p$）と書ける。$j\le p-1$ なら $d\mid2^{p-1}$ から $\omega^{2^{p-1}}=1$ となり、上の式と合わせて $R_q$ で $-1=1$、すなわち $2=0$ となる。これは $q\mid2$ を意味し、$q\ge3$ に反する。よって $d=2^p$ である。
位数 $d$ の元の冪 $\omega^0,\omega^1,\dots,\omega^{d-1}$ は $R_q^\times$ の相異なる元であり、$0\notin R_q^\times$ なので $|R_q^\times|\le q^2-1$ である。したがって
$$ 2^p=d\le|R_q^\times|\le q^2-1\le M_p-1=2^p-2 $$
となり、矛盾する。よって $M_p$ は素数である。$\square$

$p$ を奇素数とし、$q:=M_p$ が素数であると仮定する。lem-ll-residues により $q\neq3$、$\left(\frac2q\right)=1$、$\left(\frac3q\right)=-1$ である。
$R_q$ で $\tau:=1+\sqrt3$ とおく。$\tau^2=4+2\sqrt3=2\omega$ である。lem-ll-frobenius と $\left(\frac3q\right)=-1$ から $\tau^q=1-\sqrt3$ なので、
$$ \tau^{q+1}=\tau^q\cdot\tau=(1-\sqrt3)(1+\sqrt3)=-2 $$
である。$q+1=2^p$ は偶数なので、左辺は $\tau^{q+1}=(\tau^2)^{(q+1)/2}=(2\omega)^{(q+1)/2}=2^{(q+1)/2}\,\omega^{(q+1)/2}$ と書ける。一方 平方剰余 の定理「Eulerの規準」と $\left(\frac2q\right)=1$ から $2^{(q-1)/2}\equiv1\pmod q$ なので、$2^{(q+1)/2}=2\cdot2^{(q-1)/2}\equiv2\pmod q$ である。よって $R_q$ で
$$ 2\,\omega^{(q+1)/2}=-2 $$
となる。$q$ は奇素数なので $2$ は法 $q$ で逆元をもち、$\omega^{(q+1)/2}=-1$ を得る。$(q+1)/2=2^{p-1}$ なので
$$ \omega^{2^{p-1}}=-1 $$
である。両辺に $\bar\omega^{2^{p-2}}$ を掛けると、左辺は $\omega^{2^{p-2}}(\omega\bar\omega)^{2^{p-2}}=\omega^{2^{p-2}}$ となり、
$$ \omega^{2^{p-2}}+\bar\omega^{2^{p-2}}=0 $$
を得る（$p\ge3$ なので $2^{p-2}$ は正の整数である）。lem-ll-closed により左辺は整数 $s_{p-2}$ の $R_q$ での像なので、$q\mid s_{p-2}$、すなわち $M_p\mid s_{p-2}$ である。$\square$

十分性は prf-ll-sufficiency が $p$ の素数性を使わないことから従う。必要性は、$M_p$ が素数なら prf-ll-necessity がそのまま使えることから従う（そもそも $M_p$ が素数なら $p$ は素数である）。$\square$