<< Marriage | Category | Matthieu Ricard >>

Prime Numbers Infinite - Euclid Proof

|

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.

  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.

Read more

<< Marriage | Category | Matthieu Ricard >>