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, listed as [p1, …, pn].
  2. Consider the product of all the primes in the list, plus one: N = (p1 × … × pn) + 1.
  3. By construction, N is not divisible by any of the pi.
  4. Hence it is either prime itself (but not in the list of all primes), or is divisible by another prime not in the list of all primes, 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.