## Posts Tagged ‘**Euclid**’

## Infinite Beauty

In the last post I described one of the uses of large prime numbers, and added a link to the biggest yet known. It is a Mersenne prime, meaning that it is 2 to the power of another prime, minus one, and can therefore be written as 2^{43112609}-1; fully expanded, it is over twelve million digits long.

So large prime numbers are useful. And fortunately, they are an inexhaustible resource. When I say we know this for certain, I really do mean it. We are more certain of the infinitude of primes than we are of the size or age of the universe; more certain of it than we are that the Earth revolves around the sun.

Just as there are some books which everybody ought to read, there are some solutions to problems that are just so *neat* that it seems a shame not to know them. Euclid’s proof, devised over two thousand years ago, is a real glimpse of mathematical beauty.

How do we know that there are an infinite number of primes? Imagine that we don’t. We might think that the prime numbers stop after a while, and that every subsequent number is nonprime. If that were the case, there would have to be some highest-possible prime, the largest of them all. Call this ultimate über-prime *P*.

*P* stands at the head of a gigantic list of prime numbers, going all the way from *P* to the smallest prime, 2. We might arrange these numbers in order – write them down on a piece of paper longer than the universe.

2, 3, 5, 7, 11, 13 … and so on for millions of light years of paper until finally … *P*

This piece of paper contains an exhaustive list of every prime number that exists. Now imagine taking all the numbers on this list and multiplying them together, to give an even more unimaginably huge number, *R*.

2 x 3 x 5 x 7 x 11 x 13 … x *P* = *R*

*R* ends up being a number so huge that *P* seems tiny – but we know for a fact that *R* is not a prime number. We know this because *R*, divided by any prime number on our list, will leave no remainders. *R* is not prime because it is a multiple of 2 – and of 3, and of 5, and of 7, and even of *P*…

Now take this mind-blowingly, egregiously vast* *number *R* and add 1.

*R* + 1 = *Q*

What do we know about *Q*? Well, we know that if we divide it by 2, we’ll get one left over – the one we’ve just added to *R*. And if we divide it by 3, we’ll get one left over. And by 5, one left over… all the way up to *P*. If we divide *Q* by *P*, we’ll get one left over.

Which means that *Q* is a prime number – much, much bigger than *P*, the number we assumed was the largest prime. And if we take *Q* to be the largest prime, essentially making it into our *P*, we know there will be an even bigger *Q* to dwarf it.

When it comes to arguments, what could be more decisive – or as elegant – as this?

REFERENCES

This proof and others are discussed in G H Hardy’s classic essay on mathematical beauty, *A Mathematician’s Apology*. The full text can be found here.