22 Chapter 3

Sometimes one sees this argument given as a proof by contradiction, like this:

Proof. Assume toward contradiction that there are only finitely many primes, p

1

, p

2

, ...,

p

n

. Multiply them all together and add one N = p

1

p

2

···p

n

+ 1. This new number N is

not a multiple of any p

i

, and so its prime factorization must involve new primes, not on the

list, a contradiction.

Is it better to give a proof by contradiction or directly? This second proof seems per-

fectly fine. Euclid had not used proof by contradiction but, rather, proved that every finite

list of primes can be extended. Mathematicians often prefer direct proofs over proofs by

contradiction. One reason, to my way of thinking, is that direct proofs usually carry more

information about the mathematical background—they paint a fuller picture of mathemat-

ical reality. When one proves an implication p =⇒ q directly, one assumes p and derives

further consequences p

1

, p

2

, and so on, before ultimately concluding q. Thus, one has

learned a whole context about what it is like in the p worlds. Similarly, with a proof by

contraposition, one assumes the negation of the conclusion ¬q and derives consequences

about what it is like in the worlds without q, before finally concluding ¬p, negating the

hypothesis. But in a proof by contradiction, in contrast, one assumes something that ul-

timately does not hold in any world; the argument often seems to tell us little beyond the

brute fact of the implication p =⇒ q itself.

Next, let us prove that although there are infinitely many prime numbers, nevertheless

there are also long stretches of numbers with no prime numbers at all.

Theorem 17. There are arbitrarily large intervals in the positive integers containing no

prime numbers.

Proof. Consider any positive integer n ≥ 2. Notice that n! + k is a multiple of k, whenever

1 ≤ k ≤ n, since in this case it is the sum of two multiples of k. By considering 2 ≤ k ≤ n,

we have therefore found an interval of positive integers, from n! + 2upton! + n, containing

no prime numbers. This interval (inclusive) has n − 1 numbers in it, and so there are

arbitrarily large intervals of nonprimes in the positive integers.

It is natural to inquire about the density of the prime numbers. Let π(n) be the prime-

counting function, the number of prime numbers p ≤ n.

2

521

1117 2003 3119 4271 4999

The figure above illustrates the density of primes, with a narrow blue line for each prime

number up to five thousand, spaced out on the number line (some selected primes are

indicated in red). The pattern is irregular, with some intervals having primes clumped near

each other and other intervals more sparsely populated, with perhaps a barely perceptible