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 ₁ ... 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.