Prime Numbers

1.3 Primes of special form

27

passed this lg x sieve, then its probability of being prime should climb from 1/ ln x to

1

P ln x .

We know P asymptotically. It follows from the Mertens theorem (see Theorem 1.4.2) that 1/P eγ ln lg x as x → ∞. Thus, one might conclude that Mq is prime with “probability” eγ ln lg Mq / ln Mq . But this expression is very close to eγ ln q/(q ln 2). Summing this expression for primes q ≤ x, we get the heuristic asymptotic expression for the number of Mersenne prime exponents up to x, namely c ln x with c = eγ / ln 2.

If one goes back and tries to argue in a more refined way using Theorem 1.3.2, then one needs to use not only the fact that the possible prime factors of Mq are quite restricted, but also that a prime that meets the condition of this theorem has an enhanced chance of dividing Mq . For example, if p = kq + 1 is prime and p ≡ ±1 (mod 8), then one might argue that the chance that p|Mq is not 1/p, but rather the much larger 2/k. It seems that these two criteria balance out, that is, the restricted set of possible prime factors balances with the enhanced chance of divisibility by them, and we arrive at the same estimate as above. This more di cult argument was presented in the first edition of this book.

1.3.2Fermat numbers

The celebrated Fermat numbers Fn = 22n +1, like the Mersenne numbers, have been the subject of much scrutiny for centuries. In 1637 Fermat claimed that the numbers Fn are always prime, and indeed the first five, up to F4 = 65537 inclusive, are prime. However, this is one of the few cases where Fermat was wrong, perhaps very wrong. Every other single Fn for which we have been able to decide the question is composite! The first of these composites, F5, was factored by Euler.

A very remarkable theorem on prime Fermat numbers was proved by Gauss, again from his teen years. He showed that a regular polygon with n sides is constructible with straightedge and compass if and only if the largest odd divisor of n is a product of distinct Fermat primes. If F0, . . . , F4 turn out to be the only Fermat primes, then the only n-gons that are constructible are those with n = 2am with m|232 − 1 (since the product of these five Fermat primes is 232 − 1).

If one is looking for primes that are 1 more than a power of 2, then one need look no further than the Fermat numbers:

Theorem 1.3.4. If p = 2m + 1 is an odd prime, then m is a power of two.

Proof. Assume that m = ab, where a is the largest odd divisor of m. Then p has the factor 2b + 1. Therefore, a necessary condition that p be prime is that p = 2b + 1; that is, a = 1 and m = b is a power of 2.

28	Chapter 1 PRIMES!

Again, as with the Mersenne numbers, there is a useful result that restricts possible prime factors of a Fermat number.

Theorem 1.3.5 (Euler, Lucas). For n ≥ 2, any prime factor p of Fn = 22n + 1 must have p ≡ 1 (mod 2n+2).

Proof. Let r be a prime factor of Fn and let h be the least positive integer with 2h ≡ 1 (mod r). Then, since 22n ≡ −1 (mod r), we have h = 2n+1. As in the proof of Theorem 1.3.1, 2n+1 divides r − 1. Since n ≥ 2, we thus have that r ≡ 1 (mod 8). This condition implies via (2.10) that 2 is a square modulo

r, so that h = 2n+1 divides	r−2	1	, from which the assertion of the theorem is
evident.

It was this result that enabled Euler to find a factor of F5, and thus be the first to “dent” the ill-fated conjecture of Fermat. (Euler’s version of Theorem 1.3.5 had the weaker conclusion that p ≡ 1 (mod 2n+1), but this was good enough to find that 641 divides F5.) To this day, Theorem 1.3.5 is useful in factor searches on gargantuan Fermat numbers.

As with Mersenne numbers, Fermat numbers allow a very e cient test that rigorously determines prime or composite character. This is the Pepin test, or the related Suyama test (for Fermat cofactors); see Theorem 4.1.2 and Exercises 4.5, 4.7, 4.8.

By combinations of various methods, including the Pepin/Suyama tests or in many cases the newest factoring algorithms available, various Fermat numbers have been factored, either partially or completely, or, barring that, have been assigned known character (i.e., determined composite). The current situation for all Fn, n ≤ 24, is displayed in Table 1.3.

We give a summary of the theoretically interesting points concerning Table 1.3 (note that many of the factoring algorithms that have been successful on Fermat numbers are discussed in Chapters 5, 6, and 7).

(1)F7 was factored via the continued fraction method [Morrison and Brillhart 1975], while F8 was found by a variant of the Pollard-rho method [Brent and Pollard 1981].

(2)The spectacular 49-digit factor of F9 was achieved via the number field sieve (NFS) [Lenstra et al. 1993a].

(3)Thanks to the recent demolition, via the elliptic curve method, of F10 [Brent 1999], and an earlier resolution of F11 also by Brent, the smallest Fermat number not yet completely factored is F12.

(4)The two largest known prime factors of F13, and the largest prime factors of both F15 and F16 were found in recent years, via modern, enhanced variants of the elliptic curve method (ECM) [Crandall 1996a], [Brent et al. 2000], as we discuss in Section 7.4.1. The most recent factor found in this way is the 23-digit factor of F18 found by R. McIntosh and C. Tardif in 1999.

(5)The numbers F14, F20, F22, F24 (and the other C’s of the table) are, as of this writing, “genuine” composites, meaning that we know the numbers

1.3 Primes of special form		29
F0 = 3 = P
F1 = 5 = P
F2 = 17 = P
F3 = 257 = P
F4 = 65537 = P
F5	= 641 · 6700417
F6	= 274177 · 67280421310721
F7	= 59649589127497217 · 5704689200685129054721
F8	= 1238926361552897 · P
F9	= 2424833 · 7455602825647884208337395736200454918783366342657 · P

F10 = 45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P F11 = 319489 · 974849 · 167988556341760475137 · 3560841906445833920513 · P F12 = 114689 · 26017793 · 63766529 · 190274191361 · 1256132134125569 · C

F13 = 2710954639361 · 2663848877152141313 · 3603109844542291969· 319546020820551643220672513 · C

F14 = C

F15 = 1214251009 · 2327042503868417 · 168768817029516972383024127016961 · C F16 = 825753601 · 188981757975021318420037633 · C

F17 = 31065037602817 · C

F18 = 13631489 · 81274690703860512587777 · C F19 = 70525124609 · 646730219521 · C

F20 = C

F21 = 4485296422913 · C F22 = C

F23 = 167772161 · C F24 = C

Table 1.3 What is known about the first 25 Fermat numbers (as of Apr 2005); P = a proven prime, C = a proven composite, and all explicitly written factors are primes. The smallest Fermat number of unknown character is F33.

not to be prime, but do not know a single prime factor of any of the numbers. However, see Exercise 1.82 for conceptual di culties attendant on the notion of “genuine” in this context.

(6)The Pepin test proved that F14 is composite [Selfridge and Hurwitz 1964], while F20 was shown composite in the same way [Buell and Young 1988].

(7)The character of F22 was resolved [Crandall et al. 1995], but in this case an interesting verification occurred: A completely independent (in terms of hardware, software, and location) research team in South America [Trevisan and Carvalho 1993] performed the Pepin test, and obtained the same result for F22. Actually, what they found were the same Selfridge– Hurwitz residues, taken to be the least nonnegative residue modulo Fn

30	Chapter 1 PRIMES!

then taken again modulo the three coprime moduli 236, 236 − 1, 235 − 1 to forge a kind of “parity check” with probability of error being roughly 2−107. Despite the threat of machine error in a single such extensive calculation, the agreement between the independent parties leaves little doubt as to the composite character of F22.

(8)The character of F24—and the compositeness of the F23 cofactor—were resolved in 1999–2000 by Crandall, Mayer, and Papadopoulos [Crandall et al. 2003]. In this case, rigor was achieved by having (a) two independent floating-point Pepin “wavefront” tests (by Mayer and Papadopoulos, finishing in that order in August 1999), but also (b) a pure-integer convolution method for deterministic checking of the Pepin squaring chain. Again the remaining doubt as to composite character must be regarded as minuscule. More details are discussed in Exercise 4.6.

(9)Beyond F24, every Fn through n = 32 inclusive has yielded at least one proper factor, and all of those factors were found by trial division with the aid of Theorem 1.3.5. (Most recently, A. Kruppa and T. Forbes found in 2001 that 46931635677864055013377 divides F31.) The first Fermat number of unresolved character is thus F33. By conventional machinery and Pepin test, the resolution of F33 would take us well beyond the next ice age! So the need for new algorithms is as strong as can be for future work on giant Fermat numbers.

There are many other interesting facets of Fermat numbers. There is the challenge of finding very large composite Fn. For example, W. Keller showed

that F23471 is divisible by 5·223473 +1, while more recently J. Young (see [Keller 1999]) found that F213319 is divisible by 3 · 2213321 + 1, and even more recent is

the discovery by J. Cosgrave (who used remarkable software by Y. Gallot) that F382447 is divisible by 3· 2382449 + 1 (see Exercise 4.9). To show how hard these investigators must have searched, the prime divisor Cosgrave found is itself currently one of the dozen or so largest known primes. Similar e orts reported recently in [Dubner and Gallot 2002] include K. Herranen’s generalized Fermat

prime

101830214 + 1

and S. Scott’s gargantuan prime

48594216 + 1.

A compendium of numerical results on Fermat numbers is available at [Keller 1999].

It is amusing that Fermat numbers allow still another proof of Theorem 1.1.2 that there are infinitely many primes: Since the Fermat numbers are odd and the product of F0, F1, . . . , Fn−1 is Fn − 2, we immediately see that each prime factor of Fn does not divide any earlier Fj , and so there are infinitely many primes.

What about heuristic arguments: Can we give a suggested asymptotic formula for the number of n ≤ x with Fn prime? If the same kind of

1.3 Primes of special form

31

argument is made as with Mersenne primes, we get that the number of Fermat primes is finite. This comes from the convergence of the sum of n/2n, which expression one finds is proportional to the supposed probability that Fn is prime. If this kind of heuristic is to be taken seriously, it suggests that there are no more Fermat primes after F4, the point where Fermat stopped, confidently predicting that all larger Fermat numbers are prime! A heuristic suggested by H. Lenstra, similar in spirit to the previous estimate on the density of Mersenne primes, says that the “probability” that Fn is prime is approximately

	eγ lg b	,	(1.13)
	2n

where b is the current limit on the possible prime factors of Fn. If nothing is known about possible factors, one might use the smallest possible lower bound b = 3·2n+2+1 for the numerator calculation, giving a rough a priori probability of n/2n that Fn is prime. (Incidentally, a similar probability argument for generalized Fermat numbers b2n + 1 appears in [Dubner and Gallot 2002].) It is from such a probabilistic perspective that Fermat’s guess looms as ill-fated as can be.

1.3.3Certain presumably rare primes

There are interesting classes of presumably rare primes. We say “presumably” because little is known in the way of rigorous density bounds, yet empirical evidence and heuristic arguments suggest relative rarity. For any odd prime p, Fermat’s “little theorem” tells us that 2p−1 ≡ 1 (mod p). One might wonder whether there are primes such that

2p−1 ≡ 1 (mod p2),

(1.14)

such primes being called Wieferich primes. These special primes figure strongly in the so-called first case of Fermat’s “last theorem,” as follows. In [Wieferich

1909] it is proved that if

xp + yp = zp,

where p is a prime that does not divide xyz, then p satisfies relation (1.14). Equivalently, we say that p is a Wieferich prime if the Fermat quotient

qp(2) = 2p−1 − 1 p

vanishes (mod p). One might guess that the “probability” that qp(2) so vanishes is about 1/p. Since the sum of the reciprocals of the primes is divergent (see Exercise 1.20), one might guess that there are infinitely many Wieferich primes. Since the prime reciprocal sum diverges very slowly, one might also guess that they are very few and far between.

The Wieferich primes 1093 and 3511 have long been known. Crandall, Dilcher, and Pomerance, with the computational aid of Bailey, established that there are no other Wieferich primes below 4 · 1012 [Crandall et al. 1997].

32	Chapter 1 PRIMES!

McIntosh has pushed the limit further—to 16 · 1012. It is not known whether there are any more Wieferich primes beyond 3511. It is also not known whether there are infinitely many primes that are not Wieferich primes! (But see Exercise 8.19.)

A second, presumably sparse class is conceived as follows. We first state a classical result and its converse:

Theorem 1.3.6 (Wilson–Lagrange). Let p be an integer greater than one. Then p is prime if and only if

(p − 1)! ≡ −1 (mod p).

This motivates us to ask whether there are any instances of

(p − 1)! ≡ −1 (mod p2),

(1.15)

such primes being called Wilson primes. For any prime p we may assign a Wilson quotient

wp = (p − 1)! + 1 , p

whose vanishing (mod p) signifies a Wilson prime. Again the “probability” that p is a Wilson prime should be about 1/p, and again the rarity is empirically manifest, in the sense that except for 5, 13, and 563, there are no Wilson primes less than 5 · 108.

A third presumably sparse class is that of Wall–Sun–Sun primes, namely

those primes p satisfying
up−(p5) ≡ 0 (mod p2),	(1.16)

where un denotes the n-th Fibonacci number (see Exercise 2.5 for definition) and where p5 is 1 if p ≡ ±1 (mod 5), is −1 if p ≡ ±2 (mod 5), and is 0 if p = 5. As with the Wieferich and Wilson primes, the congruence (1.16) is always satisfied (mod p). R. McIntosh has shown that there are no Wall–Sun– Sun primes whatsoever below 3.2 · 1012. The Wall–Sun–Sun primes also figure into the first case of Fermat’s last theorem, in the sense that a prime exponent p for xp + yp = zp, where p does not divide xyz, must also satisfy congruence (1.16) [Sun and Sun 1992].

Interesting computational issues arise in the search for Wieferich, Wilson, or Wall–Sun–Sun primes. Various such issues are covered in the exercises; for the moment we list a few salient points. First, computations (mod p2) can be e ected nicely by considering each congruence class to be a pair (a, b) = a+bp. Thus, for multiplication one may consider an operator defined by

(a, b) (c, d) ≡ (ac, (bc + ad) (mod p)) (mod p2),

and with this relation all the arithmetic necessary to search for the rare primes of this section can proceed with size-p arithmetic. Second, factorials in

1.4 Analytic number theory

33

particular can be calculated using various enhancements, such as arithmetic progression-based products and polynomial evaluation, as discussed in Chapter 8.8. For example, it is known that for p = 240 + 5,

(p − 1)! ≡ −1 − 533091778023p (mod p2),

as obtained by polynomial evaluation of the relevant factorial [Crandall et al. 1997]. This p is therefore not a Wilson prime, yet it is of interest that in this day and age, machines can validate at least 12-digit primes via application of Lagrange’s converse of the classical Wilson theorem.

In searches for these rare primes, some “close calls” have been encountered. Perhaps the only importance of a close call is to verify heuristic beliefs about the statistics of such as the Fermat and Wilson quotients. Examples of the near misses with their very small (but alas nonzero) quotients are

p = 76843523891,	qp(2)	≡ −2 (mod p),
p = 12456646902457,	qp(2)	≡ 4 (mod p),

p = 56151923, wp ≡ −1 (mod p), p = 93559087, wp ≡ −3 (mod p),

and we remind ourselves that the vanishing of any Fermat or Wilson quotient modulo p would have signaled a successful “strike.”

1.4 Analytic number theory

Analytic number theory refers to the marriage of continuum analysis with the theory of the (patently discrete) integers. In this field, one can use integrals, complex domains, and other tools of analysis to glean truths about the natural numbers. We speak of a beautiful and powerful subject that is both useful in the study of algorithms, and itself a source of many interesting algorithmic problems. In what follows we tour a few highlights of the analytic theory.

1.4.1The Riemann zeta function

It was the brilliant leap of Riemann in the mid-19th century to ponder an entity so artfully employed by Euler,

∞	1
ζ(s) =		,	(1.17)
n=1	ns

but to ponder with powerful generality, namely, to allow s to attain complex values. The sum converges absolutely for Re(s) > 1, and has an analytic continuation over the entire complex plane, regular except at the single point s = 1, where it has a simple pole with residue 1. (That is, (s−1)ζ(s) is analytic in the entire complex plane, and its value at s = 1 is 1.) It is fairly easy to see how ζ(s) can be continued to the half-plane Re(s) > 0: For Re(s) > 1 we

34				Chapter 1 PRIMES!
have identities such as
	s		− s 1	∞
ζ(s) =				(x − x )x−s−1 dx.
	s − 1

But this formula continues to apply in the region Re(s) > 0, s = 1, so we may take this integral representation as the definition of ζ(s) for the extended region. The equation also shows the claimed nature of the singularity at s = 1, and other phenomena, such as the fact that ζ has no zeros on the positive real axis. There are yet other analytic representations that give continuation to all complex values of s.

The connection with prime numbers was noticed earlier by Euler (with the variable s real), in the form of a beautiful relation that can be thought of as an analytic version of the fundamental Theorem 1.1.1:

Theorem 1.4.1 (Euler). For Re(s) > 1 and P the set of primes,
		(1.18)
ζ(s) = (1 − p−s)−1.
p P
Proof. The “Euler factor” (1 − p−s)−1	may be rewritten as the sum of a
geometric progression: 1 + p−s + p−2s +	· · ·
	. We consider the operation of

multiplying together all of these separate progressions. The general term in the multiplied-out result will be p P p−ap s, where each ap is a positive integer or 0, and all but finitely many of these ap are 0. Thus the general term is n−s for some natural number n, and by Theorem 1.1.1, each such n occurs once and only once. Thus the right side of the equation is equal to the left side of the equation, which completes the proof.

As was known to Euler, the zeta function admits various closed-form evaluations, such as

ζ(2) = π2/6,

ζ(4) = π4/90,

and in general, ζ(n) for even n is known; although not a single ζ(n) for odd n > 2 is known in closed form. But the real power of the Riemann zeta function, in regard to prime number studies, lies in the function’s properties for Re(s) ≤ 1. Closed-form evaluations such as

ζ(0) = −1/2

are sometimes possible in this region. Here are some salient facts about theoretical applications of ζ:

(1)The fact that ζ(s) → ∞ as s → 1 implies the infinitude of primes.

(2)The fact that ζ(s) has no zeros on the line Re(s) = 1 leads to the prime number Theorem 1.1.4.

p P p−1

1.4 Analytic number theory

35

(3)The properties of ζ in the “critical strip” 0 < Re(s) < 1 lead to deep aspects of the distribution of primes, such as the essential error term in the PNT.

On the point (1), we can prove Theorem 1.1.2 as follows:

Another proof of the infinitude of primes. We consider ζ(s) for s real, s > 1. Clearly, from relation (1.17), ζ(s) diverges as s → 1+ because the harmonic

sum	1/n is divergent. Indeed,		for s > 1,
				s		≤	−	1 (s 1)
	n≤1 −	n−			=			n− n− −
	ζ(s) >
	/(s	1)			n 1/(s 1)
	≥ e−1/e				n−1		> e−1/e| ln(s − 1)|.

n≤1/(s−1)

But if there were only finitely many primes, the product in (1.18) would tend to a finite limit as s → 1+, a contradiction.

The above proof actually can be used to show that the sum of the reciprocals of the primes diverges. Indeed,

ln		(1 − p−s)−1		= −
					ln(1 − p−s) =	p−s + O(1), (1.19)
	p P				p P	p P

uniformly for s > 1. Since the left side of (1.19) goes to ∞ as s → 1+ and since p−s < p−1 when s > 1, the sum is divergent. (Compare with Exercise 1.20.) It is by a similar device that Dirichlet was able to prove Theorem 1.1.5; see Section 1.4.3.

Incidentally, one can derive much more concerning the partial sums of 1/p (henceforth we suppress the notation p P, understanding that the index p is to be a prime variable unless otherwise specified):

Theorem 1.4.2 (Mertens). As x → ∞,

	1			e−γ		(1.20)
p x 1 − p			ln x ,

≤

where γ is the Euler constant. Taking the logarithm of this relation, we have

		1	= ln ln x + B + o(1),	(1.21)
	p≤x	p

for the Mertens constant B defined as

B = γ +	p	1			1
		ln 1 − p			+ p .

36	Chapter 1 PRIMES!

This theorem is proved in [Hardy and Wright 1979]. The theorem is also a corollary of the prime number Theorem 1.1.4, but it is simpler than the PNT and predates it. The PNT still has something to o er, though; it gives smaller error terms in (1.20) and (1.21). Incidentally, the computation of the Mertens constant B is an interesting challenge (Exercise 1.90).

We have seen that certain facts about the primes can be thought of as facts about the Riemann zeta function. As one penetrates more deeply into the “critical strip,” that is, into the region 0 < Re(s) < 1, one essentially gains more and more information about the detailed fluctuations in the distribution of primes. In fact it is possible to write down an explicit expression for π(x) that depends on the zeros of ζ(s) in the critical strip. We illustrate this for a function that is related to π(x), but is more natural in the analytic theory. Consider the function ψ0(x). This is the function ψ(x) defined as

ψ(x) = pm ≤x ln p = p≤x ln p		ln p		,	(1.22)
			ln x

except if x = pm, in which case ψ0(x) = ψ(x) − 12 ln p. Then (see [Edwards 1974], [Davenport 1980], [Ivi´c 1985]) for x > 1,

	xρ	1		ln 1 − x−2
ψ0(x) = x −		− ln(2π) −			,	(1.23)
	ρ		2
ρ

where the sum is over the zeros ρ of ζ(s) with Re(ρ) > 0. This sum is not absolutely convergent, and since the zeros ρ extend infinitely in both (vertical) directions in the critical strip, we understand the sum to be the limit as T → ∞ of the finite sum over those zeros ρ with |ρ| < T . It is further understood that if a zero ρ is a multiple zero of ζ(s), it is counted with proper multiplicity in the sum. (It is widely conjectured that all of the zeros of ζ(s) are simple.)

Riemann posed what has become a central conjecture for all of number theory, if not for all of mathematics:

Conjecture 1.4.1 (Riemann hypothesis (RH)). All the zeros of ζ(s) in the critical strip 0 < Re(s) < 1 lie on the line Re(s) = 1/2.

There are various equivalent formulations of the Riemann hypothesis. We have already mentioned one in Section 1.1.5. For another, consider the Mertens function

M (x) = µ(n),

n≤x

where µ(n) is the M¨obius function defined to be 1 if n is squarefree with an even number of prime factors, −1 if n is squarefree with an odd number of prime factors, and 0 if n is not squarefree. (For example, µ(1) = µ(6) = 1, µ(2) = µ(105) = −1, and µ(9) = µ(50) = 0.) The function M (x) is related to the Riemann zeta function by

1		∞	(n)		= s	∞ M (x)		dx,	(1.24)
ζ(s)		= n=1	µns			1 xs+1