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 [p₁, …, p_n].
2. Consider the product of all the primes in the list, plus one: N = (p₁ × … × p_n) + 1.
3. By construction, N is not divisible by any of the p_i.
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.