info prev up next book cdrom email home

Lucas-Lehmer Test

A Mersenne Number $M_p$ is prime Iff $M_p$ divides $s_{p-2}$, where $s_0\equiv 4$ and

s_i\equiv{s_{i-1}}^2-2 {\rm\ (mod\ } 2^p-1)
\end{displaymath} (1)

for $i\geq 1$. The first few terms of this series are 4, 14, 194, 37634, 1416317954, ... (Sloane's A003010). The remainder when $s_{p-2}$ is divided by $M_p$ is called the Lucas-Lehmer Residue for $p$. The Lucas-Lehmer Residue is 0 Iff $M_p$ is Prime. This test can also be extended to arbitrary Integers.

A generalized version of the Lucas-Lehmer test lets

N+1=\prod_{j=1}^n {q_j}^{\beta_j},
\end{displaymath} (2)

with $q_j$ the distinct Prime factors, and $\beta_j$ their respective Powers. If there exists a Lucas Sequence $U_{\nu}$ such that
{\rm GCD}(U_{(N+1)/q_j},N)=1
\end{displaymath} (3)

for $j=1$, ..., $n$ and
U_{N+1}\equiv 0\ \left({{\rm mod\ } {N}}\right),
\end{displaymath} (4)

then $N$ is a Prime. The test is particularly simple for Mersenne Numbers, yielding the conventional Lucas-Lehmer test.

See also Lucas Sequence, Mersenne Number, Rabin-Miller Strong Pseudoprime Test


Sloane, N. J. A. Sequence A003010/M3494 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein