A trivial proof of the primality test for Mersenne primes
Fermat's Library | A really trivial proof of the Lucas-Lehmer test annotated/explained version.

Lemma 2. Let X be a 

set with a binary operation which is 

associative and has an 
identity. Then the set 

X* 
of invertible elements in Xforms a 
group. 
Proof: 
Clearly the 
identity 1 E  X8, so we have a non-empty 

set. We now have only 
to 
show that the set 

X* 
is closed under the binary operation. 

But 
if 
x1 and x2 are 
invertible elements 
with inverses x 

- 
1, x 

-1 
then x1x2 has 
inverse 
x  1Xj1. 

Lemma 3.  If G is a 

finite group then the order of an element 
is 
at 
most the order of 
the 
group. If x E  G 

and 
Xr 
= 
1 
then the order of x divides r. 

(Results 
in 
group 
theory do not get any easier than 

this. These results are 

nowhere near as deep 

as Lagrange's Theorem for example!) 
Proof of Theorem 1: Let 

Zq denote the set of integers 

modulo q, 
and X 

denote 
the set (a 

+ 
bC/: 
a, 
b 
E  Zq}. 

We can define two 
binary operations 
on 
X, namely 
addition and 
multiplication, 
in 
the obvious manner. 
So 
in 
the case of 
multiplica- 
tion, which is the one of 

interest, 
we choose 
representatives 
in 
Z[V3] 
of our 
elements of 
X 
compute the 
product 
in 
the usual 
way, (a1 
+ 
b1x/3)(a2 
+ 
b2C/i) 
as 
(a1a2 
+ 
3b1b2) 
+ 
(a1b2 
+ 
a2b1)C3 
and then reduce the coefficients modulo 
q. 
In 
the case of addition we 
obviously get an abelian group, and 

for multiplication we 
clearly have an associative 
(and commutative) binary 
operation 
with 
identity 
1. Let 

X* 
denote the group 
of invertible elements of 
X 
with 
respect to multiplication. 
Lemma 2 tells us that this is a 

group, while 
Lemma 3 
tells 
us that the order of 

any 
element of 
X* 
is at most 

q2 
- 
1, 
since 
X* 
contains at least one non-invertible 
element, namely 0. 
Now consider 
w 
= 
2 
+ 
C 
as an 
element of X. Since q 

divides 
Mp 
it follows 

that 
RMP 
c 
2P 
2, 
when viewed as an 
element of X, is 0. So 

the 
equalities 
noted 
in 
(*) 
and 
(**) 
above 
in X 

reduce to 
-o2P 
=  -1, 
and 
o2P 
= 
1 
respectively. 
It 
follows 
that 
w 
lies 
in 
X*, 
and has order 2P. For the order of 
co clearly 

divides 2P 

by 
Lemma 3 and the second 
equality, 
but 
cannot 
be 
less 
than 2P 
by 
the first. 
So 
using 
Lemma 3 
again 
we deduce that 2P 

< 
q2 
-  1. 

However 
q2 
- 
1 
< 
Mp 
- 
1= 
2P 
- 
2 and we have a 
contradiction. 
REFERENCE 
1.  M. I. Rosen, A Proof of the Lucas-Lehmer Test, Amer. Math. Monthly, 95 (1988), 

855-856. 
Department of Pure Mathematics 

The University of Liverpool 
L69 3BX, UNITED KINGDOM 
1993] 
A 
REALLY 
TRIVIAL 
PROOF  OF 
THE 
LUCAS-LEHMER 
TEST  371 

This content downloaded from 128.240.225.120 on Fri, 20 Jun 2014 11:54:59 AM
All use subject to JSTOR Terms and Conditions

