Euclid's Proof - Prime Numbers are Infinite - Found this on Burton MacKenzie's blog post Prime Motivation. I marveled at the simplicity of the Euclid's proof that there are an infinite number of prime numbers-- or more precisely, that there cannot be a largest prime number. The bonus is the Euclid proves this point by assuming there is a finite number of prime numbers. Actually, as I think about it, the only way to prove anything is to structure the hypothesis in such a way that it's antithesis can be disproved. Nassim Nicholas Taleb got into the in his book The Black Swan. Below is Burton's summary of the 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.
- Burton MacKenzie: Prime Motivation www.burtonmackenzie.com
- "2300 years ago, Euclid was able to prove that there were an infinite number of prime numbers."
Related Posts
Nassim Nicholas Taleb Philosophy Mathematics
Greg Haines — 13 June 2008, 21:59
Euclid's proof never said anything about a largest prime, even when you adjust his arguments to more conventional ones by modern standards. He argued that if you have a list of primes, then there exists a number that is indivisible by any number in the list of primes. You can't use the procedure you used iteratively in any case:
2,3,5 and 7 give 211
By your reasonining, 2,3,5,7 and 211 give 44311, which should be prime. But 44311 = 73*607. By the true reasoning, 2,3,5,7,211 are relatively prime to 44311, so there must exist a prime p which divides 44311, and the list of primes gets longer
Also, as far as your antithesis idea:
4+6=10
3+3=6
Therefore, 3+3+4=10. Where is the antithesis in that?
Proof by contradiction is just one way to show things, and is best used in situations to avoid 'messy' things, like infinitudes, four dimensional spaces.
Mathematics isn't a bunch of anecdotes, and Euclid wasn't a daydreamer. Within the thinking of his time, and perhaps even today, he was a genius
Burton MacKenZie — 16 June 2008, 10:07
Greg, I think you are misinterpreting what was written here. Euclid was not looking for an iterative prime number generator (well, he may have been, but not for this proof). You start with the assumption that there are a finite number of primes (i.e. you can exhaustively list them). A finite list of all primes implies there is one that is largest. By demonstrating that you can create a number that is not divisible by any of your 'exhaustive' list of primes, it is demonstrable that your list is not exhaustive at all, and ultimately, can never be exhaustive because the number of primes is not finite, nor is there a 'largest' one.
There is a binary premise: either the number of primes is finite or it is infinite. It can't be both. Since it is a binary premise, you can use contradiction to prove one is true by proving the other is false.
