## Lucas-Lehmer Test

A Mersenne Number is prime Iff divides , where and

 (1)

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

A generalized version of the Lucas-Lehmer test lets

 (2)

with the distinct Prime factors, and their respective Powers. If there exists a Lucas Sequence such that
 (3)

for , ..., and
 (4)

then 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

References

Sloane, N. J. A. Sequence A003010/M3494 in An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein
1999-05-25