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
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
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 ) =
(pi − 1) ≥
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.