On Lucas's Test For The Primality of Mersenne's Numbers

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 2^n-1 (2ⁿ-1), where 2ⁿ-1 is a prime. The second contribution is that of Lucas who gave a pair of theorems governing the primality of 2^4k ± 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 U_n and V_n, that the test which Lucas gave for 2^4k + 1-1 is applicable also to 2^4k - 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 = 2ⁿ-1, where n is an odd prime, is a prime if ,and only if, N divides the (n-1)-st term of the series,

S₁ = 4, S₂ = 14, S₃ = 194, ..., S_k, ...,

where S_k = S_k²_- 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 + sqrt 3, b = 1 - sqrt 3,

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

We define two sequences of integers U_r and V_r by

U_r = (a^r - b^r) / (a - b),
V_r = a^r + b^r.

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

(1) 2U_r + s = U_r V_s + V_r U_s.

(2) (-2)^s + 1 U_r - s = U_s V_r - U_r V_s.

(3) 2V_r + s = V_r V_s + 12U_r U_s.

(4) U_2r = U_r V_r.

(5) V_2r = V_r² + (-2)^r + 1.

(6) V_r² - 12U_r² = (-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 U_r if, and only if, divides r.

Proof. Let S be the set of all subscripts r for which p divides U_r. 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) U_p congruent to (3/p)    (mod p).

(8) V_p 2          (mod p).

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

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

U_p

3^{½ (p - 1)} congruent to

(3/p) (mod p).

To prove (8) we expand V_p 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 U_p + 1 U_p - 1. From (1) and (2) with r = p and s = 1 we have, since U₁ = 1 and V₁ = 2,

2U_p + 1 = 2U_p + V_p,

-4U_p - 1 = 2U_p - V_p.

Using Lemma 2, we have

-8U_p + 1 U_p - 1 = 4U_p² - V_p² congruent to

4(±1)² - 4 congruent to

0 (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 = 2ⁿ-1 be a prime. We have to show that S_n - 1 is divisible by N. Instead of the series S_k we may consider the series

8, 56, 3104, ..., Sigma

_k, ... in which Sigma

_k = 2^{2^k - 1} S_k. Then it is sufficient to show that Sigma

_n - 1 is divisible by N. Since

S_k + 1 = S_k² - 2, we have Sigma

_k + 1 =

_k² - 2^{2^k + 1}.

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

V_2^k + 1 = (V_2^k)² - 2^{2^k + 1}.

Moreover V₂ = 8 = Sigma

₁. Hence, in general,

_k = V₂.

We have to show then that V_2^n - 1 = V_{½ (N + 1)} is divisible by N. But from (5), with r = ½ (N + 1), we have

V_N + 1 = V_½²_(N + 1) - 4 · 2^{½ (N - 1)}.

Hence it is sufficient to show that

(9) V_N + 1 congruent to -4 (mod N),

since 2 is a quadratic residue of N = 8x - 1. But (9) follows from Lemma 2 and (3). In fact

2V_N + 1 = V_N V₁ + 12U_N U₁ = 2V_N + 12U_N.

To apply Lemma 2 with p = N, we note that N congruent to

1 (mod 3) and that

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

Hence we have

V_N + 1 = V_N + 6U_N congruent to

2 - 6

-4 (mod N).

Hence (9) is established. This completes the proof of necessity.

Proof of Sufficiency. Let S_n - 1 be divisible by N = 2ⁿ - 1. Then N divides

_n - 1 = 2^{2^n - 2} S_n - 1 = V_2^n - 1.

Now let p be any prime factor of N and let

be the rank of apparition of p. Then p divides U_2ⁿ since N divides U_2^n - 1 V_2^n - 1, which is U_2ⁿ by (4). By Lemma 1,

divides 2ⁿ. On the other hand,

does not divide 2^n - 1, for otherwise, by Lemma 1, p would divide U_2^n - 1 as well as V_2^n - 1. This is impossible by (6) since p is odd. Hence

= 2ⁿ. By Lemma 3,

p >

- 1 = 2ⁿ - 1 = N.

Hence p = N, so that N is a prime.

In his paper Dr. Western gives a list of Mersenne numbers 2ⁿ - 1 examined by Lucas's tests. Since this list was made, Mr. R. E. Powers ³ has applied Theorem A to 2²⁴¹ - 1 and finds this number to be composite. This leaves the characters of 2ⁿ - 1 (for n < 257) undetermined for

n = 157, 167, 193, 199, 227, and 229.

Lehigh University,
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 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.

Return to this paper's entry in Luke's Mersenne Library and Bibliography