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 $$