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_{1} = 4
and S_{n} = S_{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_{p} divides S_{p-1} (where
S_{1} = 4 and S_{n} = S_{n-1}^{2}-2),
then M_{p} is prime. Let w = 2+sqrt(3), and v
= 2-sqrt(3). Then it is trivial to show (by induction) that S_{n}
= .
So M_{p} divides S_{p-1} means there is an
integer R such that

= RM_{p}

or (after we multiply by
and subtract one)

(1)
= RM_{p}-1

and squaring

(2)
= (RM_{p}-1)^{2}.

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}[sqrt(3)]^{*} of all
the numbers a + bsqrt(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^{p}. Since the order of
an element is at most the order of the group we have

2^{p} <= q^{2} - 1 < M_{p}
= 2^{p}-1

a contradiction, completing the proof of sufficiency.