A
Proof of the Lucas-Lehmer
Test
MICHAEL
I. ROSEN*
Department of
Mathematics,
Brown
University, Providence,
Rhode Island
02912
E. Lucas proposed
and
D.
H. Lehmer proved
a very elegant test for
the
primality
of the Mersenne number
Mp
=
2
P
-
1.
Unfortunately,
it is hard to
find
a
proof
in
a
modern text. Most books which state the result do not
prove
it,
but do
prove
a
related and weaker
result, e.g. [1], [2],
and
[4].
In
[5]
a
complete
proof
is
given
which
follows
the
original proof
of D. H. Lehmer
(see [3]),
but
it
is
lengthy
and detailed.
In
this
note
I
give
a
fairly
short
proof
using
the
simplest
properties
of
algebraic
numbers. Another
proof
using algebraic
numbers was
given
long ago
in
[6].
Define a sequence
Sn
recursively by
setting
SI
=
4
and
S
2
=
S,2-
-
2.
So,
SI
=
4,
S2
=
14,
S3
=
194,
etc.
THEOREM
(LuCAs-LEHMER).
Let
p
be
a
prime
number.
Then,
Mp
=
2
P
-
1 is a
prime
if
and
only if
Mp
divides
Sp
-.
Before
giving
the
proof
we need
a few definitions. Let
T
+
T_
I _
=
T2 = 2 +
r
and
X =
T
=2 -V.
Note that
TT=
-1
and
o
=
1.
LEMMA.
S =
+
Proof. Let
Tm
=
w2 l+
2.Then
T,
=
X
+
X-
4
=
SI
and
Tm
I
=
Tm2-2.
Thus,
Tm
=
S,1
for all m.
LEMMA 2.
If
we assume
Mp
is
prime,
then
TMP+
1
-1
(mod
Mp).
Proof. The congruence
is understood
to take
place
in
the
ring
of
algebraic
integers.
We
temporarily
set
q
=
Mp.
Write
4X/T
=
1
+
r/Y,
raise
both
sides to the
qth power
and take
congruences
modulo
q.
We
find
q (q
-1)/2
_
1 + 3(q-l)/2
r
(mod
q).
Since
q
-1
(mod
8)
we have
2(q1)/2
(2/q)
1
(mod q).
Since
q
1
(mod
3)
we
have
3(q-l)/2 _ (3/q)
-1
(mod q).
It follows
that
T T-
(mod q)
and
T
l-TT-
-1
(mod
q).
We can
prove
the
theorem.
We first
prove
that
SP
I
-
0
(mod
Mp)
implies
Mp
is
prime.
This part
of the
proof makes
no
use
of
Lemma 2.
From
the
condition
Sp
-
0
(mod
Mp)
we find
2P +
_2
0
(mod
Mp)
so
that
2P-_
-1
(mod
Mp)
and
W2
=
1
(mod
Mp
).
Let
I
be a
prime
dividing Mp,
and
(1=
L
[V].
The
coset
of
w
in
((7/l(9)*
has
order
2P
by
the above
congruences.
*This
work was
partically supported by
NSF
Grant
DMS-8606407.
855
This content downloaded from 129.82.28.144 on Wed, 02 Dec 2015 13:00:37 UTC
All use subject to JSTOR Terms and Conditions
856 J. ACZtL AND ZS. PALES [November
Suppose
/
splits
in (.
Then it follows that
(61/10)*
-
(Z/lZ)*
X
(Z/IZ)*,
and so
2P
divides
1
- 1.
Thus,
1
=
1
+
2Pk for
some
k
>
1.
This
is
impossible
because
it
implies
I
>
1 + 2P >
Mp.
Suppose I stays prime in (.
Then
((/1(9)*
has order 12- 1 and 2P divides
- 1 =
(I
-
1)(1
+
1). If
I
1
(mod4) we must have 2
P
divides
I-
1, or
=
1
+
2P-1k
for
some
k >
1.
This
cannot happen since 21
>
2 +
2P
>
Mp.
If
I
3
(mod 4),
then
2
P
1
divides
I +
1
so that
1=
-1
+
2P-k for some k
>
1.
One cannot
have
k
=
1
since
2P-1
-
1 does not divide 2P
-
1. The only possible
case is
k
=
2.
Then, I
=
2P
-
1
=
MP,
and so
Mp
is prime.
Finally, suppose
Mp
is
prime. From
Lemma
2 we
have
TMp+l
-1 (mod
Mp)
orT
2P
+
1
-
0
(mod
Mp).
Since
T2
=
@, @2p1
+ 1
0
(mod
Mp).
Multiply
both
sides
of this
congruence with
w2P
and recall
(,
= 1. The result
is
S
w2P-
+
2-2
0
(mod
MP).
REFERENCES
1. G. H.
Hardy and
E. M. Wright, The
Theory of
Numbers, Oxford at the
Clarendon
Press, 1965.
2. L.
K.
Hua, Introduction
to
the
Theory
of
Numbers,
Springer-Verlag,
Berlin-Heidelberg-New
York,
1982.
3. D. H.
Lehmer, On
Lucas' test for the
primality of
Mersenne's
numbers, J. of
the
London
Math.
Soc.,
10
(1935) 162-165.
4. H.
Riessel, Prime
Numbers and
Computer Methods
for
Factorization, Birkhauser,
Boston-Basel-
Stuttgart,
1985.
5. W.
Sierpinski,
Elementary Theory of
Numbers,
Polski
Akademic Nauk.,
Warsaw, 1964.
6.
A.
E.
Western,
On Lucas' and
Pepin's tests for the
primeness
of
Mersenne
numbers,
J.
of
the London
Math.
Soc., 7 (1932)
130-137.
The
Behaviour
of
Means Under
Equal
Increments of
Their
Variables
J.
ACZEL
Department
of Pure
Mathematics,
University
of
Waterloo,
Waterloo, Ont.
Canada N2L
3G]
ZS.
PALES
Institute
of
Mathematics,
L.
Kossuth
University,
H-401 0
Debrecen,
Hungary
In
[6],
after
noting
that
the
arithmetic
(M
=
A),
geometric
(M=
G),
harmonic
(M
=
H)
means,
and
the
root-mean
square
(or
quadratic
mean
M
=
Q,
denoted in
[6]
by
R)
all
satisfy
M(a,x,...,
anX)
=
M(aj,...,
an)X
(1)
(here
and
in
what
follows,
except
in
Proposition
4,
a,,...,
an,
x
are
supposed
to be
positive), and
A(a,
+
x,***,
an
+
x)
=
A(aj,............. .
......
,
an)
+
x,
.
...(2)
This content downloaded from 129.82.28.144 on Wed, 02 Dec 2015 13:00:37 UTC
All use subject to JSTOR Terms and Conditions