A proof of the Lucas-Lehmer Test

By Chris Caldwell

Let M_p be the pth Mersenne number (so M_p = 2^p-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. M_p is prime if and only if S(p-1) ≡ 0 (mod M_p) where S₁ = 4 and S_n = S_n-1² - 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 M_p divides S_p-1 (where S₁ = 4 and S_n = S_n-1²-2), then M_p is prime. Let w = 2 + √3, and v = 2 - √3. Then it is trivial to show (by induction) that S_n = w^{2^n-1} + v^{2^n-1}. So M_p divides S_p-1 means there is an integer R such that

w^{2^p-2} + v^{2^p-2} = RM_p

or (after we multiply by w^{2^p-2} and subtract one)

(1) w^{2^p-1} = RM_p w^{2^p-2} - 1

and squaring

(2) w^{2^p} = (RM_p w^{2^p-2} - 1)².

Now, for proof by contradiction, assume M_p is composite and choose one of its prime divisors q that is not greater than its square root.

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

2^p ≤ q² - 1 < M_p = 2^p-1

a contradiction, completing the proof of sufficiency. ∎