# Lucas-Lehmer test for Mersenne primes

(Redirected from Lucas-Lehmer test)

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.

## The test

The Lucas-Lehmer test works as follows. Let Mp = 2p− 1 be the Mersenne number to test with p an odd prime. Define a sequence {si} for all i ≥ 0 by

[itex]
 s_i=
\left\{
\begin{matrix}
\\
s_{i-1}^2-2&&\mbox{otherwise.}
\end{matrix}
\right.
[itex]


The first few terms of this sequence are 4, 14, 194, 37634, ... Template:OEIS. Then Mp is prime iff

[itex]s_{p-2}\equiv0\pmod{M_p};[itex]

otherwise, Mp is composite. The number sp − 2 mod Mp is called the Lucas-Lehmer residue of p.

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy

Information

• Clip Art (http://classroomclipart.com)