Lucas-Lehmer test for Mersenne primes
梅森素数(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