Primes Never Run Out

In The Sieve of Eratosthenes we found the primes up to 100: there are 25 of them. Between 1 and 10 there are 4 primes, but between 91 and 100 there is only one, 97. The primes get rarer as the numbers grow. So perhaps, somewhere far along, they stop. Is there a last prime?

Checking can't answer this, since the numbers go on forever. It needs a proof.

Make a number from the list

About 2,300 years ago, the Greek mathematician Euclid wrote a book of mathematics called the Elements. This argument is in it. Let's follow it with small numbers first.

Suppose someone says: "The only primes are 2, 3 and 5." Multiply them all together, then add 1:

2 × 3 × 5 = 30
30 + 1 = 31

Now try dividing 31 by each prime on the list:

31 ÷ 2 = 15 remainder 1
31 ÷ 3 = 10 remainder 1
31 ÷ 5 = 6 remainder 1

The list 2, 3, 5 multiplied together to make 30, then 1 added to make 31. Below, 31 divided by 2, by 3 and by 5 each leaves a remainder of 1

Why is the remainder always 1? Because 30 is a multiple of 2, of 3 and of 5. So 31 is one more than a multiple of each of them, and that 1 is left over every time. None of the primes on the list divides 31.

Either way, a new prime

In Factor Trees we saw that every number bigger than 1 is either a prime or can be split into primes. So 31 is either a prime itself, or it is built from primes. But none of those primes can be on the list, because no prime on the list divides it.

Here 31 is a prime, and it is not on the list. Sometimes the new number is not a prime. Take the list 2, 3, 5, 7, 11, 13:

2 × 3 × 5 × 7 × 11 × 13 = 30,030, and 30,030 + 1 = 30,031
30,031 = 59 × 509, and both 59 and 509 are primes

A factor tree for 30,031, which splits into 59 and 509. Beside it, the list 2, 3, 5, 7, 11, 13, with neither 59 nor 509 on it

59 and 509 are not on the list either. Either way, the list was missing a prime.

No list is ever complete

Now the proof. Pretend there is a last prime, so that all the primes fit on one list. Multiply everything on the list and add 1. As we just saw, that number brings a prime that is not on the list. But the list had every prime. That is impossible, so the pretending was wrong: there is no last prime.

This way of proving something - pretend the opposite, and follow it to something impossible - is called proof by impossibility (or proof by contradiction). Logic Level 2 has a lesson on it, "Proof by Impossibility", which uses it to show there is no biggest number.

Euclid didn't find all the primes or check forever. His argument works for any list, however long, so it covers them all at once.

Try it at home

Start with the list 2 and 3. Multiply and add 1. Is the new number a prime?
Do the same with 2, 3, 5 and 7. Check that the new number leaves remainder 1 when divided by each of them.

Answers: 1. 2 × 3 + 1 = 7, a prime. 2. 2 × 3 × 5 × 7 + 1 = 211, which is a prime too; 211 ÷ 7 = 30 remainder 1.

Words to know

proof by impossibility (also proof by contradiction) - showing something is true by pretending the opposite and reaching something impossible

Big idea

Multiply every prime on a list and add 1: the new number leaves remainder 1 when divided by each of them, so it brings a prime the list doesn't have. No list can hold all the primes, so they never run out.