ON LUCAS'S TEST FOR THE PRIMALITY OF MERSENNE'S NUMBERS|
D. H. LEHMER ¹.
An examination of the literature on even perfect
numbers since Euclid's time reveals only two contributions to the
subject which are of genuine importance. The first of these is the
celebrated theorem of Euler to the effect that every even perfect
number is of Euclid's type
where 2n-1 is
a prime. The second contribution is that of Lucas who gave a pair
of theorems governing the primality of
24k ± 1-1.
A great deal of confusion exists in Lucas's writings about the exact
enunciation and actual proofs of these tests for primality.
Nevertheless, it is evident that Lucas was in possession of the facts
needed to prove the sufficiency of his tests. The confusion arose
from the fact that he was unable or unwilling to consider the
In 1930 the writer proved, as a by-product of an
extended theory of Lucas's functions
Vn, that the test which Lucas
gave for 24k + 1-1
is applicable also to
24k - 1-1, and that
his condition for primality is both necessary and sufficient. In fact
the theorem may be stated as follows.
N = 2n-1,
where n is an odd prime, is a prime if ,and only if, N divides the
(n-1)-st term of the series,
S1 = 4,
S2 = 14,
S3 = 194,
where Sk =
In 1932 Dr. A. E. Western
² gave a proof of this theorem by means
of the theory of algebraic numbers. It is the purpose of this paper
to give a very elementary yet self-contained proof of Theorem A.
Notation and definitions. Let
We define two sequences of integers Ur and
br) / (a - b),
ar + br.
The following identities can be easily verified by using the above
2Ur + s =
Ur Vs +
(-2)s + 1 Ur - s =
Us Vr -
2Vr + s =
Vr Vs +
(-2)r + 1.
(-2)r + 2.
The rank of apparition of the odd prime p is the least
(if it exists) for which
U is divisible by p.
In what follows p always represents a prime greater
than 3. Before proving Theorem A it is convenient to establish three
If is the rank of
apparition of p, then p divides Ur
if, and only if, divides r.
Let S be the set of all subscripts r for
which p divides Ur.
From (1) and (2) it follows that if r and s are members
of S, so also are r ± s.
Hence S coincides with the set of all integer multiples of its
least positive member . This proves Lemma 1.
(3/p) (mod p).
2 (mod p).
To prove (7) we expand Up
All the binomial coefficients are divisible by p, except the last
which is equal to unity. Hence
3½ (p - 1)
(3/p) (mod p).
To prove (8) we expand Vp
in like manner, thus
In this case all the binomial coefficients except the first are divisible
by p. Hence (8) follows at once.
If is the rank of apparition of p, then
< p + 1.
It is obviously sufficient to prove that p divides
Up + 1
Up - 1.
From (1) and (2) with r = p and s = 1 we have, since
U1 = 1
and V1 = 2,
2Up + 1 =
-4Up - 1 =
Using Lemma 2, we have
-8Up + 1
Up - 1 =
Hence Lemma 3 is proved.
Proof of Theorem A.
We are now in a position to prove Theorem A without
difficultly. The proof is in two parts.
Proof of necessity.
N = 2n-1 be a prime. We
have to show that Sn - 1
is divisible by N. Instead of the series Sk
we may consider the series
8, 56, 3104, ..., k, ...
in which k =
22k - 1
Sk. Then it
is sufficient to show that
n - 1
is divisible by N. Since
Sk + 1 =
Sk2 - 2,
k + 1 =
22k + 1.
Now if we put r = 2k in (5) we get
V2k + 1 =
22k + 1.
Moreover V2 = 8 =
1. Hence, in general,
We have to show then that V2n - 1 =
V½ (N + 1) is divisible by N.
But from (5), with r = ½ (N + 1), we have
VN + 1 =
V½2(N + 1) -
4 · 2½ (N - 1).
Hence it is sufficient to show that
VN + 1
-4 (mod N),
since 2 is a quadratic residue of N = 8x - 1. But (9)
follows from Lemma 2 and (3). In fact
2VN + 1 =
VN V1 +
12UN U1 =
To apply Lemma 2 with p = N, we note that
N 1 (mod 3)
(3/N) = -(N/3) = -(1/3) = -1.
Hence we have
VN + 1 =
2 - 6
-4 (mod N).
Hence (9) is established. This completes the proof of necessity.
Proof of Sufficiency.
Let Sn - 1 be divisible by
N = 2n - 1. Then N divides
n - 1 =
22n - 2
Sn - 1 =
V2n - 1.
Now let p be any prime factor of N and let
be the rank of apparition of p. Then p divides
U2n since N divides
U2n - 1
V2n - 1, which is
by (4). By Lemma 1, divides
2n. On the other hand,
does not divide
2n - 1, for
otherwise, by Lemma 1, p would divide
U2n - 1 as well as
V2n - 1. This is impossible by
(6) since p is odd. Hence =
By Lemma 3,
p > - 1 =
2n - 1 = N.
Hence p = N, so that N is a prime.
In his paper Dr. Western gives a list of Mersenne numbers
2n - 1 examined by
Lucas's tests. Since this list was made, Mr. R. E. Powers
³ has applied Theorem A to
2241 - 1 and finds this
number to be composite. This leaves the characters of
2n - 1
(for n < 257) undetermined for
n = 157, 167, 193, 199, 227, and 229.
Bethlehem, Pa., U.S.A.
¹ Received 5 November, 1934; read 15 November, 1934.
² "On Lucas's and Pepin's tests for the primeness of Mersenne
Journal London Math. Soc., 7 (1932), 130-137.
This paper contains a list of references to papers on the subject.
Bull. Amer. Math. So., 40 (1934), 883.