# A proof of the Lucas-Lehmer Test

Let M_{p} be the *p*th
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_{1}= 4 and S= S_{n}_{n-1}^{2}- 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

divides S_{p}_{p-1}(where S_{1}= 4 and S= S_{n}_{n-1}^{2}-2), then Mis prime. Let_{p}*w*= 2 + √3, and*v*= 2 - √3. Then it is trivial to show (by induction) that S= w_{n}^{2n-1}+ v^{2n-1}. So Mdivides S_{p}_{p-1}means there is an integer R such thatw

^{2p-2}+ v^{2p-2}= RM_{p}or (after we multiply by w

^{2p-2}and subtract one)(1) w

^{2p-1}= RMw_{p}^{2p-2}- 1and squaring

(2) w

^{2p}= (RMw_{p}^{2p-2}- 1)^{2}.Now, for proof by contradiction, assume M

is composite and choose one of its prime divisors_{p}*q*that is not greater than its square root.Consider the group G = Z

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

≤^{p}*q*^{2}- 1 < M= 2_{p}-1^{p}a contradiction, completing the proof of sufficiency. ∎