A proof of the Lucas-Lehmer Test 
(From the Prime Pages' list of proofs)


Home
Search Site

Largest
The 5000
Top 20
Finding
How Many?
Mersenne

Glossary
Prime Curios!
Prime Lists

FAQ
e-mail list
Titans

Submit primes

Let Mp be the pth Mersenne number (so Mp = 2p-1).  These numbers are (and always have been) central to the studies of prime numbers (see the pages on Mersenne numbers).  What concerns us here is a test for their primality first devised by Lucas then simplified by Lehmer:
Lucas-Lehmer Test (1930).
Let p be an odd prime.  Mp is prime if and only if S(p-1) = 0 (mod Mp) where S1 = 4 and Sn = Sn-12-2.
The proof is similar to most of the classical tests and relies on the fact that the order of an element divides the order of the group. We separate the proof into two parts (I have not yet typed in the proof of the necessity.)

Proof of the sufficiency.

We will follow Bruce's proof [Bruce93] that if the Mersenne Mp divides Sp-1 (where S1 = 4 and Sn = Sn-12-2), then Mp is prime. Let w = 2+sqrt(3), and v = 2-sqrt(3). Then it is trivial to show (by induction) that Sn = w^2^(n-1)+v^2^(n-1). So Mp divides Sp-1 means there is an integer R such that
w^2^(p-2)+v^2^(p-2) = RMp
or (after we multiply by w^2^(p-2) and subtract one)
(1)   w^2^(p-1) = RMpw^2^(p-2)-1
and squaring
(2)   w^2^p = (RMpw^2^(p-2)-1)2.
Now, for proof by contradiction, assume Mp is composite and choose one of its prime divisors q that is not greater than its square root.

Consider the group G = Zq[sqrt(3)]* of all the numbers a + bsqrt(3) modulo q which are invertible. Note G has at most q2-1 elements. Viewing w modulo q, the equalities (1) and (2) above become w2p-1 = -1 and w2p = 1 respectively, showing w is an element of G with order 2p. Since the order of an element is at most the order of the group we have

2p <= q2 - 1 < Mp = 2p-1
a contradiction, completing the proof of sufficiency.
The Prime Pages
Another prime page by Chris K. Caldwell <caldwell@utm.edu>