Monday, June 29, 2009

How Many Prime Numbers are There?

Prime numbers, most of us have heard of them. Primes are those special numbers which are only divisible by its self and 1 (i.e. 2 is only divisible by 2, 7 is only divisible by 7, 179424673 is only divisible by 179424673, and so on). It is believed that the Ancient Greeks were the first to study them and we today continue to use them for encryption and other important things to modern day life.

The Egyptians maybe able to lay claim to have discover prime numbers, but it is with the ancient Greeks that we get a lot of what we are thought in school about primes. Pythagoras' school study primes for their beauty and mystical and numerological properties. Euclid showed in his 9 book of Elements that there are infinitely many primes.

Simple proof of the infinite number of primes:

Assume there are only a finite number of primes, such that p1, p2, p3, ..., pn are all the prime numbers that exist. Given p1 * p2 * p3 * ... * pn + 1 = P, we know that P must be larger than any of the finite number of primes, therefore P must be divisible by one of our finite number of primes. Here lays the problem, if P is divide by any of the finite number of primes then there must be a remainder of 1 (i.e. 2 * 3 * 5 * 7 + 1 divided by either 2, 3, 5, or 7 would have to leave a remainder of 1 (go head try it on a calculator), the plus 1 is the issue). This is a contradiction, therefore there must not be a finite number of primes and thus we have an infinite number of primes.

This simple proof is similar to what Euclid gave in his 9th book of Elements. It is based on the fact that numbers keep on going and that giving a list of numbers we can create new numbers that are not on that list. So the argument is that given a list of prime numbers we can find a prime number that is not on the list by simply taking the prime numbers on the list multiplying them and adding 1 to the total (note, this does not mean that the multiple of a number of different prime numbers plus 1 is prime, just that is a good way of finding another prime number).

For example take 2, 3, and 5. (2 * 3) + 1 = 7, which is prime. (2 * 3 * 5) + 1 = 31, which is also prime. (3 * 5) + 1 = 16, which is not prime. (If you think that all you need is 2 and another prime, then try (2 * 7) + 1 = 15, which is not prime.)

I hope I have shown you that there are an infinite number of prime numbers. Now go out there and find them you could win money if you find a really large one!