Ever since I first encountered it at school, I’ve always admired the elegant simplicity of the reductio ad absurdum proof of the irrationality of the square-root of two. I know, I know: I really should get out more.
This week’s New Scientist includes a description of Euclid‘s equally elegant and simple, 2,300-year-old, reductio ad absurdum proof that there is an infinite number of prime numbers. I hadn’t seen it before. It’s really neat. The description goes as follows:
Suppose a mathematician comes with a finite list of primes and claims there are no more. Euclid showed that there must be a prime missing from the list. Multiply all the primes on the list together and then add one to this number. This new number is not divisible by any of the primes on the list because you always get remainder one. So Euclid’s new number is either another prime itself or divisible by a prime that is missing from the list. If you add this new prime to the list, repeating Euclid’s trick will always show that any finite list is missing a prime.
Sorry to bore you with maths. The real reason I’m doing it is because I just thought of the here’s looking at Euclid pun, and I really didn’t want to let it to go to waste.