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