2 1. Elementary Prime Number Theory, I

The first half of this chapter is a survey of the many proofs that have

been given for Theorem 1.1. The second half of this chapter is devoted to the

theme of prime-producing formulas and the occurrence of primes in various

natural sequences.

2. Euclid and his imitators

We begin with the classic proof from Euclid’s Elements (circa 300 BC):

Proof. Suppose that p1,p2,...,pk is any finite list of primes. Let P denote

the product of the pi and consider the integer P +1. Since P +1 ≡ 1 (mod pi)

for each 1 ≤ i ≤ k, none of the pi divide P +1. But since P +1 1, it must

have some prime divisor p. It follows that there is always a prime missing

from any finite list, or, as Euclid put it, “prime numbers are more than any

assigned multitude of primes.”

There are many trivial variants; for instance, we can easily show that for

every integer m there is a prime p m by taking p to be any prime divisor

of m! + 1.

In this section we collect several Euclidean proofs for Theorem 1.1. All

of these start with a finite list of primes and then produce an integer 1

that is coprime to every prime on the list. Stieltjes’s proof is typical:

Stieltjes’s proof, 1890. Suppose that p1,...,pk is a finite list of distinct

primes with product P and let P = AB be any decomposition of P into two

positive factors. Suppose that p is one of the pi. Then p | AB, so that either

p | A or p | B. If p divides both A and B, then

p2

divides P , which is false.

Consequently, p divides exactly one of A and B. It follows that p A + B.

So A + B is divisible by none of the pi; but as A + B ≥ 2, it has some prime

divisor. So again we have discovered a prime not on our original list.

Euler’s second proof (published posthumously). This proof is based

on the multiplicativity of the Euler totient function: Let p1,...,pk be a list

of distinct primes with product P . By said multiplicativity,

ϕ(P ) =

k

i=1

(pi − 1) ≥

2k−1

≥ 2,

provided that our list contains at least two primes (as we may assume). It

follows that there is an integer in the interval [2,P ] that is coprime to P ;

but such an integer has a prime factor distinct from all of the pi.