4_245_Jaroma.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 2, No. 3, 2009, (352-360) ISSN 1307-5543 – www.ejpam.com Equivalence of Pepin’s and the Lucas-Lehmer Tests John H. Jaroma Department of Mathematics & Physics, Ave Maria University, Ave Maria, Florida, 34142, UNITED STATES Abstract. Pepin’s test provides a necessary and sufficient condition for a Fermat number to be prime. The Lucas-Lehmer test does similarly for a Mersenne number. These tests share a common nature. However, this is evident neither by their usual statements nor their usual treatment in the literature. Furthermore, it is unusual to even find a proof of the latter result in elementary textbooks. The intent of this paper is to bring to light the equivalent structure of these two primality tests. 2000 Mathematics Subject Classifications: 11A41, 11A51, 11B39 Key Words and Phrases: Primes, primality test, Lehmer sequence, Pepin’s test, Lucas-Lehmer test. 1. Introduction A Fermat number is any integer of the form Fn = 22n + 1, where n ≥ 0. They are named in honor of Pierre de Fermat (1601–1665) who had expressed a belief that such numbers are always prime. In 1732, Leonhard Euler negatively resolved http://www.ejpam.com 352 c© 2009 EJPAM All rights reserved. John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 353 Fermat’s assertion by factoring F5. Today, the prevailing conjecture appears to be that no Fermat primes beyond n = 4 exist. A necessary and sufficient condition for the primality of a Fermat number is provided by Pepin’s test. It is named after Fr. Théophile Pepin (1826–1904) and is found in textbooks often stated along the lines of Fn is prime if and only if 3 Fn−1 2 ≡ −1 (mod Fn) [1], [11], or [15]. A Mersenne number is any integer given by Mn = 2n−1, where n ≥ 1, and so called because of a rather accurate conjecture made by Fr. Marin Mersenne (1588–1648) who asserted that such numbers are prime for n ∈ {2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257} and composite for all other values of n ≤ 257. It took mathematicians more than 300 years to completely resolve the conjecture. Upon having done so, we learned that Mersenne had made only five mistakes. The Lucas-Lehmer test provides a necessary and sufficient condition for a Mersenne number to be prime. Letting p denote a prime, the test is often described as Mp is prime if and only if rp−1 ≡ 0 (mod Mp), where r1 = 4, and for k ≥ 2, rk = r2 k−1 − 2 (mod Mp), 0 ≤ rk < Mp. For instance [1], [13] or [14]. Although not evident by their usual statements alone, both Pepin’s test and the Lucas-Lehmer test are inherently derived from the properties of the Lehmer sequences with both tests being demonstrable by similar arguments. The intent of this note to make the common structure of these two tests more widely known. The similarity between the two primality tests appears to have been overlooked. For example, in [10], Pepin’s test is discussed after the section Primality tests based on the Lucas sequences.∗ In addition, in [3], Derrick Lehmer opts not to illustrate a test for the primality of the Fermat numbers but instead remarks in particular we could give new tests for the primality of 22n + 1, but those Fermat numbers which have not already been tested are too large for the application of any known test. Having said this, Pepin’s test is never explicitly mentioned in Lehmer’s paper. Lastly, in [16], Williams ∗The Lucas sequences are special cases of the Lehmer sequences, where R is a perfect square. John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 354 cites that Pepin had been aware that the earlier version of his test, N = 2r + 1 is prime if and only if 5 N−1 2 ≡ −1 (mod N), could be made into a simple Lucas-like test by defining T1 = 52 and Ti+1 = T 2 i , where i is a positive integer. This leads to the result that Fn is prime if and only if Fn | Tr−1+ 1. However, a direct correlation to the Lucas-Lehmer result does not appear to be given in the book. 2. The Lehmer Sequences Let R and Q be relatively prime integers. The Lehmer sequences {Un( p R,Q)} and the companion Lehmer sequences {Vn( p R,Q)} are defined respectively, by Un+2( p R,Q) = p RUn+1 −QUn, U0 = 0, U1 = 1, n ∈ {0, 1, . . .} (2.1) Vn+2( p R,Q) = p RVn+1 −QVn, V0 = 2, V1 = p R, n ∈ {0, 1, . . .}. (2.2) Furthermore, since (2.1) and (2.2) are linear, they are solvable and given explicitly by (2.3) and (2.4), respectively. Un( p R,Q) = θ n−φn θ −φ , n ∈ {0, 1, . . .} (2.3) Vn( p R,Q) = θ n+φn, n ∈ {0, 1, . . .} (2.4) where, θ = p R+ p R−4Q 2 and φ = p R− p R−4Q 2 . We say that the rank of apparition of a number N in a sequence is the index of the first term in that sequence that contains N as a divisor. N is said to have maximal rank of apparition provided that its rank of apparition is either N ± 1. 3. Properties of the Lehmer Sequences Let p denote an arbitrary odd prime such that p ∤ RQ. The following propositions are divisibility properties associated with the Lehmer sequences found in [3]. John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 355 Lemma 3.1. The greatest common factor of Un( p R,Q) and Vn( p R,Q) is 1 or 2. Let p be an odd prime and a any integer not divisible by p. Then, the Legendre symbol (a/p) is defined to be 1 provided that a is a quadratic residue modulo p and -1 if a is a quadratic nonresidue modulo p. For all a such that (a, p) = 1, a is called a quadratic residue modulo p if the congruence x2 ≡ a (mod p) has a solution. Otherwise, a is called a quadratic nonresidue modulo p. If p | a then (a/p) = 0. Consider the Legendre symbols σ = (R/p) and ε = (∆/p), where ∆ = R− 4Q is the discriminant of the characteristic equation of (2.1) and (2.2). Lemma 3.2. Let p ∤ RQ. Then, Up−σε( p R,Q)≡ 0 (mod p). Let ω(p) denote the rank of apparition of p in {Un( p R,Q)}. The next result tells us that every term with index equal to a multiple of ω must also contain p as a factor. Lemma 3.3. Let ω denote the rank of apparition of p in the sequence {Un( p R,Q)}. Then, p | Un( p R,Q) if and only if n = kω, where k ∈ {1, 2, . . .}. So far, we have seen that almost any odd prime will divide infinitely many terms of {Un( p R,Q)}. However, there are infinitely many p which do not divide {Vn( p R,Q)}. Lemma 3.4. Suppose that ω is odd. Then Vn( p R,Q) is not divisible by p for any value of n. On the other hand, if n is even, say 2k, then V(2n+1)k( p R,Q) is divisible by p for every n but no other terms of the sequence contain p as a factor. Let λ(p) denote the rank of apparition of p in {Vn( p R,Q)}. Lemma 3.5. Let p ∤ RQ∆. Then, U p−σε 2 ( p R,Q)≡ 0 (mod p) if and only if σ = τ, where τ= (Q/p). Lemma 3.6. Let p ∤ 2RQ∆. If N ± 1 is the rank of apparition of N then N is prime. John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 356 4. Historical Background In order to acquire a more complete understanding of these two tests, we consider them first in their historical contexts. In 1877, Fr. Pepin formulated the following theorem [7]: Theorem 4.1. Pepin’s Test (Original Version) The Fermat number, Fn = 22n +1, where n > 1 is prime if and only if 5 Fn−1 2 ≡−1 (mod Fn). Pepin had noted in [7] that the number 10 could be used in place of 5. Prior to Pepin’s remark, François Proth (1852 – 1879) noted in 1876 and then again in 1878 that one may use the number 3 in lieu of 5 for our Theorem 4.1 [8], [9]) but offered no proof of his assertion. Then, Édouard Lucas (1842 – 1891) commented that an arbitrary integer a could be used in place of 5 provided that the Jacobi symbol (a/Fn) has a value equal to -1 [5] and in 1879 offered a proof [6]. Thus, the result we now call Pepin’s test is actually a theorem suggested by Proth and proved by Lucas. For a more detailed summary of these events, the reader is directed to [16], where a more detailed account is found. A modern version of Pepin’s test is given by: Theorem 4.2. Pepin’s Test (Modern Version) The Fermat number, Fn = 22n +1, where n ≥ 1 is prime if and only if 3 Fn−1 2 ≡−1 (mod Fn). Testing primality of the Mersenne numbers was initiated by Lucas in 1878. Lucas proposed two tests for determining if 2n − 1 is prime [5]. However, neither theorem John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 357 was given as necessary and sufficient. In 1930, D. H. Lehmer wrote, his [Lucas’s] conditions for primality are sufficient but not necessary.† One is uncertain whether Lu- cas’ tests will reveal the character of a number which is actually a prime [3]. Lehmer furthermore noted that R. D. Carmichael in [2] had provided a set of necessary and sufficient conditions for the primality of such numbers. However, with the exception of two cases, they depended on the existence of an auxiliary pair of numbers to be used in testing a given integer. Thus, according to Lehmer, from a practical point of view these tests are not applicable since no method is given for determining in advance an appropriate number pair. Finally, in response to his own observation Lehmer produced an explicit necessary and sufficient condition for a Mersenne number to be prime [3]. This result today is commonly known as the Lucas-Lehmer test. The original statement of this celebrated result is found in [3], although it had been mistakenly noted in [13] that Lehmer’s original proof of the Lucas-Lehmer test is given in [4]. Theorem 4.3. Lucas-Lehmer Test (Original Version) The number, Mn = 2n − 1, is prime if and only if it divides the (n− 1)st term of the sequence 4, 14, 194, 37634, 1416317954, . . . Sk, . . . where, Sk = S2 k−1− 2. 5. Equivalence of Pepin’s and the Lucas-Lehmer Tests We are ready to show that Pepin’s and the Lucas-Lehmer tests share a similar structure. To this end, we make the observation that {Vn(4, 3)} = 3n+ 1. This follows subsequently from Theorem 5.1. †Although Lucas did not attempt to give necessary tests, one of them is in fact necessary. John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 358 Theorem 5.1. Let a be any integer. Then the terms of the companion Lehmer sequence {Vn( p R,Q)} = {Vn(a+ 1, a)} are of the form an + 1. The proof is straightforward in light of (2.4) by letting p R = a + 1 and Q = a, and is omitted. Hence, the terms of {Vn(4, 3)} are Vn = 3n + 1. So, VFn−1 2 = 3 Fn−1 2 . Thus, Theorem 4.2 is revised equivalently by the statement of Theorem 5.2. Its proof requires the following identity found in [3]. U2n = UnVn (5.1) Theorem 5.2. Pepin’s Test The Fermat number Fn = 22n + 1 where, n ≥ 1 is prime if and only if Fn | VFn−1 2 (4, 3). Proof. Consider {Vn(4, 3)}. Then, ∆ = R− 4Q = 16− 12 = 4. Letting Fn = 22n + 1 be prime, it follows that ε = � ∆ Fn � = � 4 Fn � = � 2 Fn �� 2 Fn � = 1 and σ = � R Fn � = � 16 Fn � = � 4 Fn �� 4 Fn � = 1. Furthermore, since n > 1, by Gauss’s Reciprocity Law, � 3 Fn � � Fn 3 � = � 3 22n +1 �� 22n +1 3 � = (−1) 3−1 2 · 22n +1−1 2 = (−1)2 n−1 = 1. Hence, � 3 Fn � = � Fn 3 � . Thus, τ = � Q Fn � = � 3 Fn � = � Fn 3 � ≡ � 22n + 1 � 3−1 2 ≡ −1 (mod 3). Since σε = 1, then by Lemma 3.2, Fn | U22n . Because τ 6= σ, it follows by Lemma 3.5 that Fn ∤ U22n−1 . Thus, the rank of apparition of Fn in {Un(4, 3)} is 22n ; that is, Fn− 1. (Otherwise, by Lemma 3.3 the rank of apparition is 22n−r , for some positive integer r. Also by Lemma 3.3, Fn | U2n−1 .) Therefore, by Lemma 3.4, Fn | VFn−1 2 . Conversely, let’s suppose Fn | VFn−1 2 . Then by (5.1), Fn | UFn−1. Specifically, Fn | U22n . By Lemma 3.3, ω(Fn) must be a divisor of 22n . But by Lemma 3.1, U22n is relatively prime to U22n−1 . Thus, ω(Fn) = 22n = Fn− 1. Therefore, by Lemma 3.6, Fn is prime. Next, we show that the sequence of numbers 4, 14, 194, 37634, 1416317954, . . . given in Theorem 4.3 are the terms of the companion Lehmer sequence {Vn( p 2,−1)} John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 359 whose indices are powers of 2. But first, the following identity found in [3] is needed. V2n = V 2 n − 2Qn. (5.2) Now, consider {Vn( p 2,−1)}. So, V2 = 4. Furthermore, from Theorem 4.3 Sk = S2 k−1 − 2, where S1 = 4 = V2. Since Q = −1, by (5.2) it follows that Sk = V2k for k ∈ {1, 2, . . .}. Hence, the statement given in the Lucas-Lehmer Test asserting Mn divides the (n− 1)st term of 4, 14, 194, 37634, 1416317954, . . . then Mn is a factor of V2n−1 is equivalent to saying that Mn | VMn+1 2 . Thus, we now state the following equivalent form of Theorem 4.3. Theorem 5.3. Lucas-Lehmer Test The number Mn = 2n − 1, where n > 2 is prime if and only if Mn | VMn+1 2 ( p 2,−1). Proof. As R = 2, Q = −1, and ∆ = 6, it follows that ε = −1, σ = 1, and τ = −1. The proof then follows similarly to that presented for Theorem 5.2. It may be found in [3]. References [1 ] D. M. Burton, Elementary Number Theory, 6th ed., McGraw-Hill, New York, 2005. [2 ] R. D. Carmichael, On the numerical factors of the arithmetic forms αn±βn, Ann. Math. 2nd Ser. 15: 30–70 (1913). [3 ] D. H. Lehmer, An extended theory of Lucas’ functions, Ann. Math. 31: 419–448 (1930). [4 ] D. H. Lemer, On Lucas’ test for the primality of Mersenne’s numbers, J. Lon. Math. Soc. 10: 162–165 (1935). [5 ] É. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1: 184–240, 289–321 (1878). [6 ] É. Lucas, Question 453, Nouv. Cor. Math. 5: p.137 (1879). John H. Jaroma / Eur. J. Pure Appl. Math, 2 (2009), (352-360) 360 [7 ] T. Pepin, Sur la formule 22n + 1, Comp. Rend. Acad. Sci. 85: 329–331 (1877). [8 ] F. Proth, Énoncés de divers théorèmes sur les nombres, Comp. Rend. Acad. Sci. 83: 1288–1289 (1876). [9 ] F. Proth, Mémoires présentés, Comp. Rend. Acad. Sci. 87: p.374 (1878). [10 ] P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, New York, 1996. [11 ] N. Robbins, Beginning Number Theory, Wm. C. Brown, Dubuque, 1993. [12 ] K. H. Rosen, Elementary Number Theory, 4th ed., Addison Wesley Longman, Reading, 2000. [13 ] M. Rosen, A proof of the Lucas-Lehmer test, Amer. Math. Mon. 95: 855–856 (1988). [14 ] P. Schumer, Introduction to Number Theory, PWS, Boston, 1996. [15 ] J. J. Tattersall, Elementary Number Theory in Nine Chapters, 2nd ed., Cambridge Univ. Press, Cambridge, 2005. [16 ] H. C. Williams, Édouard Lucas and Primality Testing, John Wiley & Sons, New York, 1998.