Saturday, February 09, 2013

Big, bigger, biggest

One of my favourite quotes from The Simpsons is when Bart says "This is the worst day of my life" and Homer looks lovingly at him and says "The worst day of your life so far".  This jumped into my mind when I saw a headline reading "Largest prime number discovered" and without thinking I said to myself "Largest prime number discovered so far".  So is there such a thing as the largest prime number?  The Greek mathematician Euclid over two thousand years ago looked at this problem, decided that the answer was no, and came up with one of his clever proofs.  It relies on the fact that any number is either prime, or if not it is the result of multiplying two or more prime numbers together,  OK said Euclid, let's suppose there is a biggest prime number - call it P. So the list of prime numbers goes 2,3,5,7,11,13... and so on up to and including P.  Now multiply all these numbers together and call the answer N.  N is obviously bigger than P. Create a new number by adding 1 to N.  Consider this new number N+1.  Now N+1 is either prime, or it is the product of primes, in which case it must be exactly divisible by these primes. If it's prime, then you've proved that there is a bigger prime number than P.  If it's not prime then it must be divisible by primes, but because of the way it was created it can't be exactly divisible by any of the primes up to and including P - all of which would leave a remainder of 1.  So the primes it is the product of must be greater than P - QED as they say.

No comments: