ON LUCAS'S TEST FOR THE PRIMALITY OF MERSENNE'S NUMBERS

D. H. L
EHMER ¹.

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 2n-1 (2n-1), 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 necessity also.
In 1930 the writer proved, as a by-product of an extended theory of Lucas's functions Un and 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.

THEOREM A.    The number 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,   ...,   Sk,   ...,

where Sk = Sk2- 1-2

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

 a = 1 + 3,   b = 1 - 3, so that a + b = 2,   ab = -2,   a - b = 2 3.

We define two sequences of integers Ur and Vr by

Ur = (ar - br) / (a - b),
Vr = ar + br.

The following identities can be easily verified by using the above definitions.

 (1) 2Ur + s = Ur Vs + Vr Us. (2) (-2)s + 1 Ur - s = Us Vr - Ur Vs. (3) 2Vr + s = Vr Vs + 12Ur Us. (4) U2r = Ur Vr. (5) V2r = Vr2 + (-2)r + 1. (6) Vr2 - 12Ur2 = (-2)r + 2.

DEFINITION.    The rank of apparition of the odd prime p is the least positive subscript (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 lemmas.

LEMMA 1.    If is the rank of apparition of p, then p divides Ur if, and only if, divides r.

Proof.    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.

LEMMA 2.
 (7) Up  (3/p)    (mod p). (8) Vp  2          (mod p).

Proof.    To prove (7) we expand Up as follows:

All the binomial coefficients are divisible by p, except the last which is equal to unity. Hence

Up  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.

LEMMA 3.    If is the rank of apparition of p, then  < p + 1.

Proof.    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 = 2Up + Vp,

-4Up - 1 = 2Up - Vp.

Using Lemma 2, we have

-8Up + 1 Up - 1 = 4Up2 - Vp2 4(±1)2 - 40     (mod p).

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.    Let 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,
we have
k + 1 = k2 - 22k + 1.

Now if we put r = 2k in (5) we get

V2k + 1 = (V2k)2 - 22k + 1.

Moreover V2 = 8 = 1. Hence, in general,

k = V2.

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

 (9) 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 = 2VN + 12UN.

To apply Lemma 2 with p = N, we note that N  1 (mod 3) and that

(3/N) = -(N/3) = -(1/3) = -1.

Hence we have

VN + 1 = VN + 6UN  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 U2n 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  = 2n. 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.

Lehigh University,
Bethlehem, Pa., U.S.A.

² "On Lucas's and Pepin's tests for the primeness of Mersenne numbers", 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.