The proof, for any list

\text{Assume the primes are } p_1, p_2, \dots, p_n

N = p_1 p_2 \cdots p_n + 1

N \div p_i \text{ leaves remainder } 1

\text{so } N\text{'s prime factors are not on the list}

a contradiction, so the list was never complete (and N need not be prime itself: 30 031 isn't)

Proof

The primes never run out.

Euclid proved it about 2300 years ago, and the proof still works the same way: assume the opposite, follow it carefully, and watch it break. Here it is on real numbers first.

scroll ↓

Assume the opposite

Suppose there were only six primes: $2, 3, 5, 7, 11$ and $13$ . Each row marks the multiples of one of them, across the whole numbers from $30\,020$ to $30\,042$ .

Multiply them

Their product is a multiple of every one of them, so it sits on every row at once.

2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30\,030

Add one

One step on, $30\,031$ misses every row. It is one more than a multiple of each prime, so dividing by any of them leaves remainder 1. None of the six divides it.

Contradiction

But every whole number above $1$ has a prime factor, and $30\,031 = 59 \times 509$ . Both are primes that are not on the list, so the six were never all the primes.

Any list at all

Nothing depended on the six. Start from any finite list, multiply, add one, and the result has a prime factor the list is missing. No finite list holds every prime, so there are infinitely many.

Chapter 1

Assume it's false. Watch it break.

Proof by deduction, by exhaustion and by counter-example, why $\sqrt{2}$ is irrational, and twelve graded exam questions with full worked solutions are waiting.

Read the full chapter › Jump to the questions ›