Sunday, October 28, 2007
2300 years ago, Euclid was able to prove that there were an infinite number of prime numbers . This was thousands of years before steam engines, before knowing what gravity is, before knowing what the Sun is, before knowing that disease is caused by microscopic animals and viruses. Modern knowledge of mathematics far predates its application. The ancient Greeks like Euclid were cutting edge mathematicians, "[they] first spoke a language which modern mathematicians can understand." 
To prove primes are infinite, Euclid chose to disprove the opposite: that primes are finite. It's a really simple proof:
- Assume that prime numbers are finite and that "P" is the largest prime. For the sake of example, let's say the largest prime number is P = 7. That would mean that 2, 3, 5, and 7 are the only prime numbers, and 7 is the largest of them; that there are no prime numbers bigger than 7.
- Create a new number, "Q", by multiplying all the known primes together, and adding "1". e.g. Q = (2 * 3 * 5 * 7) +1 = 211
- Divide Q by any of the known prime numbers. It will never divide evenly and always have a remainder of "1". e.g. 211/2 = 105R1, 211/3 = 70R1, 211/5 = 42R1, and 211/7 = 30R1
- If a number is indivisible by any primes, that means that it, itself, is a prime number.
- P = 7 cannot be the largest prime because Q = 211 is larger than P and is prime. This is true for any value of P.
- Therefore, there cannot be a largest prime. Reductio Ad absurdum, our initial assumption that there can be a "largest" prime is incorrect. The prime numbers go on forever.
Another interesting feature of the landscape of prime numbers is an Ulam spiral. If you plot them just right, the spacial distribution of prime numbers has a pattern detectable by humans with the naked eye.
To get the pattern shown above, list numbers sequentially in a square-spiral way and plot a point at each prime number you find.  This pattern was discovered by accident by a doodling mathematician (Stanislaw Ulam) in an allegedly boring meeting.
The late mathematician Paul Erdos is reported to have said "God may not play dice with the universe, but something strange is going on with the prime numbers."
Burton MacKenZie http://www.burtonmackenzie.com/
 "Elements IX 20. The real origin of many theorems in the Elements is obscure, but there seems to be no particular reason for supposing that this one is not Euclid's own", G.H.Hardy, "A Mathematician's Apology", Cambridge University Press, 1940, p. 92.
 G.H.Hardy, "A Mathematician's Apology", Cambridge University Press, 1940, p.81.
 Licensed under the GFDL by the original author; Released under the GNU Free Documentation License.