# A Proof of the Lucas-Lehmer Test

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/a-proof-of-the-lucas-lehmer-test

- **Authors:** Michael I. Rosen
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1459715781296-eg1et2pe2jt62y1i-dc6792fae13aca31ff28a74a9629585d%2Frosen1988.pdf
- **Pages:** 2
- **Annotations:** 0 comments in 0 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/a-proof-of-the-lucas-lehmer-test

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

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

#### Page 2

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

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/a-proof-of-the-lucas-lehmer-test. More annotated papers: https://fermatslibrary.com/llms.txt
