The Lucas-Lehmer test for Mersenne primes reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Lucas-Lehmer test for Mersenne primes

In mathematics, the Lucas-Lehmer test is a primality test for Mersenne numbers. The test was originally developed by Edouard Lucas in 1878 and subsequently improved by Derrick Henry Lehmer in the 1930s.

Table of contents

1 The test 2 See also 3 External links

The test

The Lucas-Lehmer test works as follows. Let M_p = 2^p− 1 be the Mersenne number to test (then presumably p is prime, otherwise M_p is composite). Define a sequence {s_i} for all i ≥ 0 by

The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence A003010 in OEIS). Then M_p is prime iff

otherwise, M_p is composite. The number s_{p − 2} mod M_p is called the Lucas-Lehmer residue of p.

See also

• Lucas-Lehmer primality test

External links

• MathWorld: Lucas-Lehmer test

This is the "Lucas-Lehmer test for Mersenne primes" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.