In 300 AD Euclid proved that there is an infinite number of primes. A prime number being an integer that is not divisible by any other numbers. The list of prime numbers starts like this: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...
A guy 1700 hundred years ago could prove that this list goes on forever. A colleague, Adam Straub, challenged me to re-derive this without any resources. Adam argued: a person in the 21st century should be able to recreate this simple proof. I was able, but it took some time while driving. I challenge any readers to prove that there is an infinite number of primes before reading the solution. It is a fun challenge that requires middle school level math.
Euclid's Proof:
If we have a list of consecutive primes, starting with 2, 3, 5, .... and so on. We can always prove there is one more prime by multiplying them all together and adding one. We know this knew number is not divisible by any of the primes in our original list. So, either the new number is prime, or it is divisible by a new prime not in our original list.
Example: 2 * 3 * 5 + 1 = 31
So, if we know there is always one more prime in a consecutive list of primes there is always more primes, on to infinity.
I tried to explain this proof as simply as possible, but you can look up Euclid's proof on many other sites or even his original book, Elements (Book IX, Proposition 20) published circa 300 AD.
Wednesday, November 18, 2009
Subscribe to:
Posts (Atom)