# 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.