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."
|Math Proofs Demystified - by Stan Gibilisco|