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
= .
So Mp divides Sp-1 means there is an
integer R such that
= RMp
or (after we multiply by
and subtract one)
(1)
= RMp-1
and squaring
(2)
= (RMp-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.
.
So Mp divides Sp-1 means there is an
integer R such that
.gif){kind=small}
and subtract one)
= RMp .gif){kind=small}
= RMp
= (RMp