问题

梅森素数(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