math lessons - 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.

The test

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

$s_i= \left\{ \begin{matrix} 4,\qquad\ \,&&\mbox{if }i=0;\ \ \, \\ s_{i-1}^2-2&&\mbox{otherwise.} \end{matrix} \right.$

The first few terms of this sequence are 4, 14, 194, 37634, ... . Then M_p is prime iff

$s_{p-2}\equiv0\pmod{M_p};$

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