Euclid's proof that there are an infinite number of primes

(by reductio ad absurdum )

  1. Assume there are a finite number, n , of primes , the largest being p n .
  2. Consider the number that is the product of these, plus one: N = p 1 ... p n +1.
  3. By construction, N is not divisible by any of the p i .
  4. Hence it is either prime itself, or divisible by another prime greater than p n , contradicting the assumption.
  5. q.e.d.

For example:

  1. 2 + 1 = 3, is prime
  2. 2*3 + 1 = 7, is prime
  3. 2*3*5 + 1 = 31, is prime
  4. 2*3*5*7 + 1 = 211, is prime
  5. 2*3*5*7*11 + 1 = 2311, is prime
  6. 2*3*5*7*11*13 + 1 = 30031 = 59*509
  7. 2*3*5*7*11*13*17 + 1 = 510511 = 19*97*277
  8. 2*3*5*7*11*13*17*19 + 1 = 9699691 = 347*27953
  9. 2*3*5*7*11*13*17*19*23 + 1 = 223092871 = 317*703763
  10. 2*3*5*7*11*13*17*19*23*29 + 1 = 6469693231 = 331*571*34231
  11. 2*3*5*7*11*13*17*19*23*29*31 + 1 = 200560490131, is prime
  12. 2*3*5*7*11*13*17*19*23*29*31*37 + 1 = 7420738134811 = 181*60611*676421
  13. etc.