Infinitely Many Primes

The sieve lists the primes up to any bound, and they keep coming: 2, 3, 5, 7, 11, … but they also thin out. Could they stop altogether? Euclid answered this around 300 BC with one of the most famous arguments in mathematics, a proof by contradiction.

Theorem. There are infinitely many primes.

Why it works

Suppose there were only finitely many: $p_1, p_2, \dots, p_k$. Let $$N = p_1 p_2 \cdots p_k + 1.$$ Since $N > 1$, it has a prime factor $q$ (its smallest divisor above 1 is prime, or use unique factorization). Could $q$ be one of the $p_i$? Then $q$ would divide both $N$ and $p_1 \cdots p_k$, so it would divide their difference, $1$. That is impossible. So $q$ is a prime that is not on the list, contradicting the assumption that the list had every prime.

Read carefully, the proof gives a recipe: any finite list of primes misses one, and the prime factors of $N$ are new. It does not say that $N$ itself is prime.

Worked example: The new prime may be N itself

Apply the recipe to the list $2, 3, 5$.

$N = 2 \cdot 3 \cdot 5 + 1 = 31$.
$31$ is prime, and it is not on the list.

Answer: $31$.

Worked example: Or a small prime that was left out

Apply the recipe to the list $3, 5$.

$N = 3 \cdot 5 + 1 = 16 = 2^{4}$.
$N$ is not prime, but its prime factor $2$ is missing from the list. The recipe still works.

Answer: The new prime is $2$.

Worked example: A famous composite

Is $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ prime?

$N = 30{,}030 + 1 = 30{,}031$. None of $2, 3, 5, 7, 11, 13$ divides it: each leaves remainder $1$.
Keep testing primes: $17, 19, \dots, 53$ all leave remainders, and then $30{,}031 = 59 \cdot 509$.
So $N$ is composite, but both of its prime factors are new, exactly as the proof promised.

Answer: No: $30{,}031 = 59 \cdot 509$.

Common mistake

Thinking that $p_1 p_2 \cdots p_k + 1$ must be prime. It need not be: $30{,}031 = 59 \cdot 509$. The proof never claims it is prime; it only uses that it has some prime factor, and that no listed prime can be that factor.

The same idea proves more. Every prime factor of $n! + 1$ is larger than $n$ (each prime up to $n$ leaves remainder 1), so there is always a prime above any $n$. A variation with $N = 4p_1 \cdots p_k - 1$ shows there are infinitely many primes of the form $4k + 3$.

Euclid's theorem was only the start. In 1837 Dirichlet proved that whenever $\gcd(a, b) = 1$, the progression $a, a + b, a + 2b, \dots$ contains infinitely many primes, for example infinitely many primes end in the digit 7. His proof needed calculus; Euclid's needs one line of algebra.

Key idea

Multiply any finite list of primes and add 1. The result has a prime factor that is not on the list, so no list can contain them all.

Sources and further reading

William Stein, Elementary Number Theory: Primes, Congruences, and Secrets (Springer, 2009; free online edition), chapter 1, Prime Numbers (there are infinitely many primes)

Lehman, Leighton and Meyer, Mathematics for Computer Science (MIT OpenCourseWare 6.042J), chapter on number theory: prime numbers

Infinitely Many Primes

Practice

Builds on

Leads to

Sources and further reading