A proof of the Lucas-Lehmer Test
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 + √3, and v = 2 - √3. Then it is trivial to show (by induction) that Sn = w2n-1 + v2n-1. So Mp divides Sp-1 means there is an integer R such that
w2p-2 + v2p-2 = RMp
or (after we multiply by w2p-2 and subtract one)
(1) w2p-1 = RMp w2p-2 - 1
(2) w2p = (RMp w2p-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[√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. ∎