Lucas-Lehmer test

A test for the primality of Mersenne numbers.

Define the sequence 4, 14, 194, 37634, ... inductively as follows:

$$ E_1 = 4 \\ E_{k+1} = E_k^2 - 2 $$

Then the \(p\)th Mersenne number is prime precisely when \( E_{p-1} \) is zero modulo \( M_p \) :

$$ p,M_p : \mathbb{N} \mid p>2 \land M_p=2^p-1 \vdash M_p \in \mbox{prime} \iff E_{p-1} \mbox{mod} M_p = 0 $$

• E. Lucas. Unpublished work, in the 1870s
• D. H. Lehmer. Published proofs of the theorem, in the 1930s.

• Hardy & Wright. Theory of Numbers, section 15.5
• Kranakis. Primality and Cryptography, section 2.9
• Stepney. Prime Candidates