问题及解答

梅森素数(Mersenne primes)的 Lucas-Lehmer 测试.

设 $M_p=2^p-1$ 是梅森数(Mersenne number), $p$ 是大于 2 的素数. 定义序列 $\{s_i\}_{i=0}^{\infty}$:

\[
s_n=\begin{cases}
4, & n=0,\\
s_{n-1}^2 -2, & n > 0.
\end{cases}
\]

即 $s_0=4$, $s_1=14$, $s_2=194$, $s_3=37634$, 等等. (参见 OEIS A003010) 于是我们有.

定理. $M_p=2^p-1$ 是素数当且仅当 $s_{p-2}\equiv 0\bmod M_p$.

等价的, 如果令 $s_1=4$, $s_n=s_{n-1}^2-2$, 则叙述改为 $M_p=2^p-1$ 是素数当且仅当 $s_{p-1}\equiv 0\bmod M_p$.

证明的关键是令 $w=2+\sqrt{3}$, $v=2-\sqrt{3}$, 从而可证明

\[
s_n=w^{2^{n-1}}+v^{2^{n-1}}.
\]

注意 $w\cdot v=1$.

References:

https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test

https://primes.utm.edu/notes/proofs/LucasLehmer.html

($\Leftarrow$ 充分性)

这里是沿用 Bruce 的证明. 假设 Mersenne 数 $M_p$ 整除 $s_{p-1}$, 我们要证明 $M_p$ 为素数.

令 $w=2+\sqrt{3}$, $v=2-\sqrt{3}$. 于是 $w\cdot v=1$, 并且有 $s_n=w^{2^{n-1}}+v^{2^{n-1}}$. 这个只需归纳法证明即可.

事实上, $s_1=w^{2^{0}}+v^{2^{0}}=w+v=4$ 成立, $s_2=w^{2^{1}}+v^{2^{1}}=(2+\sqrt{3})^2+(2-\sqrt{3})^2=14$. 

假设 $s_k=w^{2^{k-1}}+v^{2^{k-1}}$ 成立, 则

\[
\begin{split}
s_{k+1}&=s_k^2 -2\\
&=\Bigl(w^{2^{k-1}}+v^{2^{k-1}}\Bigr)^2 -2\\
&=w^{2^k}+2(wv)^{2^{k-1}}+v^{2^k}-2\\
&=w^{2^{k}}+v^{2^{k}}
\end{split}
\]

由条件 $M_p | s_{p-1}$, 得存在数 $R\in\mathbb{Z}^{+}$, 使得

\[
w^{2^{p-2}}+v^{2^{p-2}}=R\cdot M_p.
\]

两边乘以 $w^{2^{p-2}}$, 得

\[
w^{2^{p-1}}=R\cdot M_p\cdot w^{2^{p-2}}-1.\qquad (1)
\]

对此式两边再平方, 得

\[
w^{2^{p}}=\Bigl(R\cdot M_p\cdot w^{2^{p-2}}-1\Bigr)^2.\qquad (2)
\]

使用反证法. 假设 $M_p$ 是合数, 选取其某个素因子 $q\leqslant\sqrt{M_p}$. 考虑群 $G=Z_q[\sqrt{3}]^*$. (其中的元素形如 $\bar{a}+\bar{b}\sqrt{3}$, 这里 $\bar{a}=a\bmod q$.)

注意到群 $G$ 至多有 $q^2-1$ 个元素. 在模 $q$ 下, (1) 和 (2) 变为

\[
\begin{cases}
w^{2^{p-1}}\equiv -1\bmod q,\\
w^{2^{p}}\equiv 1\bmod q.\\
\end{cases}
\]

这表明, $w\in G$, 且 $\mathrm{ord}w=2^{p}$. (注意 $w=2+\sqrt{3}$.)

由于元素的阶不超过群的阶(群中元素总个数). 故我们有

\[
2^p\leqslant q^2-1 < M_p=2^p-1.
\]

矛盾. 故 $M_p=2^p-1$ 是素数.

“充分性”译自 https://primes.utm.edu/notes/proofs/LucasLehmer.html

($\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