From M. I. Rosen, "A Proof of the Lucas-Lehmer Test," American Mathematical Monthly, 81 (1988), 855-856.

Definition. Let S₁ = 1 and S_n+1 = S_n² - 2 for n >= 1.

Lucas-Lehmer Test. Let p be a prime number. Then, M_p = 2^p-1 is prime if and only if M_p divides S_p-1 .

Definitions. Let t = (1 + sqrt(3))/ sqrt(2), u = (1 - sqrt(3))/ sqrt(2) and w = t² = 2 + sqrt(3), v = u² = 2 - sqrt(3) .

Note that tu = -1 and wv = 1.

Lemma. S_m = w^{2^m-1} + v^{2^m-1} .

Proof. By induction on m.

Lemma 2. If we assume M_p is prime, then t^{M_p + 1} = -1 (mod M_p) .

Proof. The congruence is understood to take place in the ring of algebraic integers. We temporarily set q = M_p.

Write sqrt(2) t = 1 + sqrt(3), raise both sides to the qth power and take congruences modulo q. We find

t^q w^(q-1)/2 sqrt(2) = 1 + 3^(q-1)/2 sqrt(3) (mod q) .

Since q = -1 (mod 8) we have

2^(q-1)/2 = (2/q) = 1 (mod q) .

Since q = 1 (mod 3) we have

3^(q-1)/2 = (3/q) = -1 (mod q) .

It follows that

t^q = u (mod q) and t^q+1 = tu = -1 (mod q) .

We can now prove the theorem. We first prove that S_p-1 = 0 (mod M_p) implies M_p is prime. This part of the proof makes no use of Lemma 2. From the condition S_p-1 = 0 (mod M_p) we find w^{2^p-2} + v^{2^p-2} = 0 (mod M_p) so that w^{2^p-1} = -1 (mod M_p) and v^{2^p} = 1 (mod M_p) . Let l be a prime dividing M_p, and O = Z[ sqrt(3) ]. The coset of w in (O/lO)^* has order 2^p by the above congruences. Suppose l splits in O. Then it follows that (O/lO)^* = (Z/lZ)^* x (Z/lZ)^* , and so 2^p divides l-1. Thus, l = 1 + 2^pk for some k >= 1. This is impossible because it implies l >= 1 + 2^p > M_p . Suppose l stays prime in O. Then (O/lO)^* has order l² - 1 and 2^p divides l² - 1 = (l-1)(l+1). If l = 1 (mod 4) we must have 2^p-1 divides l-1, or l = 1 + 2^p-1 k for some k >= 1. This cannot happen since 2l >= 2 + 2^p > M_p. If l = 3 (mod 4), then 2^p-1 divides l+1 so that l = -1 + 2^p-1 k for some k >= 1. One cannot have k = 1 since 2^p-1 - 1 does not divide 2^p - 1. The only possible case is k=2. Then, l = 2^p - 1 = M_p, and so M_p is prime. Finally, suppose M_p is prime. From Lemma 2 we have t^{M + 1} = -1 (mod M_p) or t^{2^p} + 1 = 0 (mod M_p). Since t² = w, w^{2^p-1} + 1 = 0 (mod M_p). Multiply both sides of this congruence with v^{2^p-2} and recall wv = 1. The result is S_p-1 = w^{2^p-2} + v^{2^p-2} = 0 (mod M_p) .