Prove there are infinitely many primes Step by Step

Step by step

Question: prove that there are infinitely many primes.

Suppose the opposite: there are only a few primes.

Call them p 1, p 2, up to p k.

Suppose the only primes are p₁, p₂, ..., p_k.

Careful!

N itself does not have to be prime.

But its prime factors are not on the list.

Careful: N need not be prime: its prime factors are new

Multiply them all, then add 1.

Call it N.

N = p₁ × p₂ × ... × p_k + 1

Divide N by any prime on the list: the product goes in exactly, and 1 is left over.

N ÷ each prime on the list: remainder 1

But N is bigger than 1, so it has a prime factor.

We saw that with factor trees.

N > 1 has a prime factor

That prime factor cannot be on the list: they all leave 1.

So the list was not all the primes!

that prime factor is not on the list ✗

The opposite led to nonsense, so the primes never run out.

So there are infinitely many primes. ∎

Try the list 2, 3, 5: N is 31, a prime not on the list.

2 × 3 × 5 + 1 = 31: a new prime

A longer list: 30031 is 59 times 509.

Not prime, but 59 and 509 are new primes.

Right!

2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509

Let's look back.

First: assume the opposite.

Then: work it out.

Then: find the contradiction.

Last: check.

Answer

So there are infinitely many primes. ∎