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 LucasLehmer Residue for
. The LucasLehmer Residue is 0 Iff is Prime. This test can also be extended to arbitrary
Integers.
A generalized version of the LucasLehmer 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
LucasLehmer test.
See also Lucas Sequence, Mersenne Number,
RabinMiller Strong Pseudoprime Test
References
Sloane, N. J. A. Sequence
A003010/M3494
in ``An OnLine 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.
© 19969 Eric W. Weisstein
19990525