Prime numbers are more than any assigned multitude of prime numbers.

— Euclid, Elements, Proposition IX.20

A prime number is an integer greater than 1 that can only be divided by 1 and by itself: 2, 3, 5, 7, 11, 13, … All the others, such as $12=2\cdot2\cdot3$, are products of primes. The primes are the atoms of arithmetic.

The further you go, the rarer they become. Between 1 and 100 there are 25 primes; between 1,000,001 and 1,000,100, only 6. Do they run out at some point? Euclid showed that they do not, with a four-line argument that the English mathematician G. H. Hardy considered one of the most beautiful in all of mathematics.

The proof

Suppose someone gives you a finite list of primes, $p_1,p_2,\ldots,p_n$. Euclid shows that there is at least one prime outside the list. Multiply them all and add 1:

$$N=p_1\cdot p_2\cdots p_n+1.$$

Now divide $N$ by any prime in the list. The product $p_1p_2\cdots p_n$ is divisible by it, so the remainder of the division of $N$ is 1. No prime in the list divides $N$.

But $N$ is greater than 1, so it has at least one prime divisor $q$. Why? Take the smallest divisor of $N$ greater than 1. If it were not prime, it would have a smaller divisor, which would also divide $N$, contradicting the choice. So the smallest divisor is prime.

This prime $q$ divides $N$, and no prime in the list divides $N$. So $q$ is not in the list. No finite list contains all the primes:

$$\boxed{\text{there are infinitely many primes.}}$$

Euclid does not speak of “infinity”, a word the Greeks avoided. He says that, given any number of primes, there are more. It is the same thing, said carefully.

The number constructed is not always prime

A common mistake is to think that $N$ is always prime. Look:

List $N$ Is $N$ prime?
2 3 yes
2, 3 7 yes
2, 3, 5 31 yes
2, 3, 5, 7 211 yes
2, 3, 5, 7, 11 2,311 yes
2, 3, 5, 7, 11, 13 30,031 no: $30{,}031=59\cdot509$

In the sixth row, $N$ is composite. But its factors, 59 and 509, are primes not in the list. The proof never said $N$ is prime; it said only that some new prime divides $N$. To this day it is not known whether the list in the table produces infinitely many primes or not.

A similar proof, for squares

The same style of argument, assuming something and reaching a contradiction, proves that $\sqrt2$ is not a fraction, another result discussed in Book X of the Elements. If $\sqrt2=\frac pq$ with the fraction in lowest terms, then $p^2=2q^2$; $p^2$ is even, so $p$ is even, $p=2k$; hence $4k^2=2q^2$, $q^2=2k^2$, and $q$ is even too. But the fraction was in lowest terms. Contradiction.

Exercise: start from the list 3, 5. What number does the construction produce, and what new prime does it reveal?

$N=3\cdot5+1=16=2^4$. The number is composite, and its only prime factor, $2$, is not in the list. The proof works with any list, even one that does not start with 2.

Exercise: show that there are runs of 5 consecutive numbers with no prime.

Take $6!=720$. The numbers $720+2$, $720+3$, $720+4$, $720+5$ and $720+6$ are divisible by 2, 3, 4, 5 and 6 respectively. None is prime. With $(n+1)!$ one gets, in the same way, $n$ consecutive composite numbers. The primes never run out, but they can be as far apart as you like.

Sources: Elements, Proposition IX.20, D. E. Joyce’s edition · G. H. Hardy, A Mathematician’s Apology (Cambridge, 1940) · GIMPS, Great Internet Mersenne Prime Search.

All topics on Euclid · ← Euclid’s algorithm: the greatest common divisor · The fifth postulate and the other geometries →

Image credits.