## Sunday, October 28, 2007

### Prime Motivation

2300 years ago, Euclid was able to prove that there were an infinite number of prime numbers [1]. 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." [2]

To prove primes are infinite, Euclid chose to disprove the opposite: that primes are finite. It's a really simple proof:

1. 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.
2. Create a new number, "Q", by multiplying all the known primes together, and adding "1". e.g. Q = (2 * 3 * 5 * 7) +1 = 211
3. 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
4. If a number is indivisible by any primes, that means that it, itself, is a prime number.
5. 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.
6. 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.
If there's an infinite number of primes, there's not much point in trying to enumerate all of them, but it feels like we should be getting less and less of them as we count higher and higher. That is, more or less, what happens. The Prime number theorem (2nd link to more rigorous explanation, 3rd link for emprical findings) gives us an asymptotic logarithmic distribution of prime numbers. The larger the number is, the smaller the chance it's going to be a prime number.

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. [3] 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."

Strange, indeed.

Burton MacKenZie http://www.burtonmackenzie.com/

[1] "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.

[2] G.H.Hardy, "A Mathematician's Apology", Cambridge University Press, 1940, p.81.

[3] Licensed under the GFDL by the original author; Released under the GNU Free Documentation License.

IvyMike said...

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.

The number Q, created by multiplying all the known primes up to P and adding 1, is not itself necessarily prime. It's just got a factor that's bigger than P. (In your example, P=7, Q does turn out to be prime. But had you chosen P=13, 2*3*5*7*11*13+1 = 30031 = 59 × 509)

Anwitaman said...

Q itself need not be prime (for the proof to work). All the proof is saz=ying is, if P was indeed the largetst prime, hwo come it is not divisible by any of the prime numbers less than or equal to P. ... So P is not the largest prime (proof by contradiction).

jeroen94704 said...

The proof as phrased here can be misleading, since Q itself does not have to be prime itself. Instead, the proof relies on the fact that all non-prime numbers can be constructed by multiplying a set of primes. In this proof, if Q cannot be composed by multiplying any combination of the known primes, this means it is EITHER itself prime, OR that there is/are more primes somewhere between P and Q that would allow Q to be constructed.

The counter-example of P=13 shows this: 30031 cannot be constructed by multiplying primes from the set ASSUMED to contain all primes. This means that either this number is prime itself, or there are primes >13 which can construct this number. The latter turns out to be the case, as 59*509 = 30031, and both 59 and 509 are prime.

jeroen94704 said...

As an aside, the rule that all non-prime number can be constructed as the product of zero or more primes is called the Fundamental Theorem of Arithmetic. Euclid also proved this using the "proof by contradiction" method.

Justin said...

Hey Burton. You have in your article "disease is caused by microscopic animals". I think you meant microorganisms. Bacteria and other microorganisms are not in the Animalia kingdom.

Felix said...

Hey Burton. You have in your article "thousands of years before the steam engine". I think you meant hundreds.
http://en.wikipedia.org/wiki/Aeolipile

Dan Kurt said...

If you are interested in Prime Numbers do a google search on this:

james mccanney calculate primes

Next, open up the first listed link.

robert said...

Ummm is the idea of primes being infinite really that impressive? .... It seems rather intuitive its about as impressive as proving odd or even numbers infinite ( and really is nothing but an extension of that very argument )

Andrew Horton said...

james mccanney is a fraud... or at least I assume so as I didn't buy his book to make certain.

burton mackenzie said...

Sorry it's taken so long to reply.

ivymike:
By definition in the problem set up, Q must be prime, because there are no primes bigger than P. Q cannot have a factor bigger than P because that factor would necessarily be composed of the "known" (and finite) primes, or be prime itself, which would also satisfy the intent of the proof. To use your example, 30031 is divisible by 59, but 59 is a prime number, which means there is a prime bigger than 13, which is the point of this whole proof. It is reductio ad absurdum, which means "reduced to the absurd", thus the assumption of a "largest prime" is false.

Anwitaman:
exactly. the algorithm for Q is not useful for actually determining primes. It's only useful for discrediting the concept of finite primes. Thanks!

Justin:
You're correct, I did mean to say "microscopic organisms" and not "microscopic animals", but I've spent a lot of time lately explain things to a toddler, and "animals" is an easier concept. It was my mistake. That being said, I am no biologist.

felix:
Thanks for the steam engine info - it was an arbitrary example, but I didn't know about that early one.

robert:
Yes, it is important to know whether or not the primes are infinite. It isn't at all like the argument you present. The integers are infinite (aelph-naught), and since every second integer is odd (or even), then necessarily odd or even numbers are also infinite. However, with prime numbers, the higher you count, the less and less prime numbers you encounter. Without actually knowing (i.e. have it proven), it is conceivably possible that at some point there are no more prime numbers left and all remaining numbers are factorable into the existing set of (finite) prime numbers. (i.e. prime factorization) This proof settles the matter. The primes go on forever, but until this proof (in recorded history), nobody knew that for sure.

simple_solutions said...

I understand Euclid's proof of the infinite numbers; however, what if we were to modify this proof to say...there are infinitely many prime numbers of the form 4n+3. Also, try 4n+1. Why would 4n+3 work where 4n+1 fails?
I'm reading a book that talks about it but I really don't know why one works and the other fails. Any help would be great!