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

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.