Wednesday, November 18, 2009

An Inifinite Number of Primes

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.

2 comments:

Tim Rondeau said...

I know I'm a little late on reading this, but you have made a mistake (either with your wording or your proof, I'm not sure which). You implied that taking the product of any finite set of primes and adding one will yield a new prime number. This is not true. In fact, finding the product of the first 6 primes and adding 1 (30,031) is not prime. I'm sure you were just referring to that as the general concept behind the proof, but I thought I would make sure.

Hovden said...

You're right, I left out the complete explanation, and an important detail. It has been added.