($\Rightarrow$ 必要性)
设 $M_p=2^p-1$ 是素数, 这里 $p$ 是奇素数. 回忆对于任何大于 1 的奇数 $p$ 有 $2^p-1\equiv 7\bmod 12$ (见问题1750), 我们设 $2^p=12K+8$. 利用 Legendre 符号的性质, 得
\[
\Bigl(\frac{3}{M_p}\Bigr)=(-1)^{\lfloor\frac{M_p+1}{6}\rfloor}=(-1)^{\lfloor\frac{2^p}{6}\rfloor}=(-1)^{\lfloor\frac{12K+8}{6}\rfloor}=(-1)^{2K+1}=-1.
\]
换言之, $3$ 不是模 $M_p$ 的平方剩余 (non-residue module $M_p$). 根据 Euler 判断准则, 这等价于
\[
3^{\frac{M_p-1}{2}}\equiv -1\pmod M_p
\]
相反的, $2$ 是模 $M_p$ 的平方剩余. 因为 $2^p\equiv 1\pmod M_p$, 从而 $2^{p+1}\equiv 2\pmod M_p$, 注意 $p+1$ 是偶数.
由 Euler 判断法则, 得
\[2^{\frac{M_p-1}{2}}\equiv 1\pmod M_p .\]
于是,
\[
24^{\frac{M_p-1}{2}}\equiv\Bigl(2^{\frac{M_p-1}{2}}\Bigr)^3\cdot\Bigl(3^{\frac{M_p-1}{2}}\Bigr)\equiv 1^3\cdot(-1)=-1\pmod M_p .
\]
令 $\sigma=2\sqrt{3}$, 令 $X=\{a+b\sqrt{3}\mid a,b\in\mathbb{Z}_{M_p}\}$, $X$ 是一个环. 在环 $X$ 中, 我们计算
\[
\begin{split}
(6+\sigma)^{M_p}&=(6+2\sqrt{3})^{M_p}\\
&=6^{M_p}+\sum_{i=1}^{M_p-1}C_{M_p}^{i}6^{M_p-i}(2\sqrt{3})^i+(2\sqrt{3})^{M_p}\\
&=6^{M_p}+2^{M_p}\cdot(\sqrt{3})^{M_p}\\
&=6+2\cdot(\sqrt{3})^{M_p-1}\cdot\sqrt{3}\\
&=6+2\cdot 3^{\frac{M_p-1}{2}}\cdot\sqrt{3}\\
&=6-2\sqrt{3}=6-\sigma.
\end{split}
\]
这里注意到 $M_p|C_{M_p}^{i}$, 对于 $i=1,2,\ldots, M_p-1$. 以及 $6^{M_p-1}\equiv 1\pmod M_p$. 也就是用到了有限域中的二项式定理 $(x+y)^{M_p}\equiv x^{M_p}+y^{M_p}\equiv\pmod M_p$ 以及 Fermat 小定理 $a^{M_p-1}\equiv 1\pmod M_p$, 其中 $M_p$ 是素数.
令 $w=\frac{(6+\sigma)^2}{24}$. 这样令的原因是要满足 $w\bar{w}=1$. 这里 $\bar{w}=\frac{(6-\sigma)^2}{24}$.
在环 $X$ 中, 我们计算 $w^{\frac{M_p+1}{2}}$.
\[
\begin{split}
w^{\frac{M_p+1}{2}}&=\biggl[\frac{(6+\sigma)^2}{24}\biggr]^{\frac{M_p+1}{2}}\\
&=\dfrac{(6+\sigma)^{M_p+1}}{24^{\frac{M_p+1}{2}}}\\
&=\dfrac{(6+\sigma)\cdot(6+\sigma)^{M_p}}{24\cdot 24^{\frac{M_p-1}{2}}}\\
&=\frac{(6+\sigma)(6-\sigma)}{24\cdot(-1)}\\
&=\frac{36-\sigma^2}{-24}\\
&=\frac{36-(2\sqrt{3})^2}{-24}\\
&=-1.
\end{split}
\]
两边乘以 $\bar{w}^{\frac{M_p+1}{4}}$, 并利用 $w\bar{w}=1$, 得
\[
\begin{split}
&w^{\frac{M_p+1}{2}}\cdot\bar{w}^{\frac{M_p+1}{4}}\equiv -\bar{w}^{\frac{M_p+1}{4}}\\
\Rightarrow\ &w^{\frac{M_p+1}{4}}\cdot 1\equiv -\bar{w}^{\frac{M_p+1}{4}}\\
\Rightarrow\ &w^{\frac{M_p+1}{4}}+\bar{w}^{\frac{M_p+1}{4}}\equiv 0\\
\Rightarrow\ &w^{\frac{2^p-1+1}{4}}+\bar{w}^{\frac{2^p-1+1}{4}}\equiv 0\\
\Rightarrow\ &w^{2^{p-2}}+\bar{w}^{2^{p-2}}\equiv 0\\
\Rightarrow\ &s_{p-2}\equiv 0\pmod M_p.
\end{split}
\]
证明译自 https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test