home
>
factoids
> Infinite number of primes
Euclid's proof that there are an infinite number of primes
(by
reductio ad absurdum
)
Assume there are a finite number,
n
, of
primes
, the largest being
p
_{ n }
.
Consider the number that is the product of these, plus one:
N
=
p
_{ 1 }
...
p
_{ n }
+1.
By construction,
N
is not divisible by any of the
p
_{ i }
.
Hence it is either prime itself, or divisible by another prime greater than
p
_{ n }
, contradicting the assumption.
q.e.d.
For example:
2 + 1 = 3, is prime
2*3 + 1 = 7, is prime
2*3*5 + 1 = 31, is prime
2*3*5*7 + 1 = 211, is prime
2*3*5*7*11 + 1 = 2311, is prime
2*3*5*7*11*13 + 1 = 30031 = 59*509
2*3*5*7*11*13*17 + 1 = 510511 = 19*97*277
2*3*5*7*11*13*17*19 + 1 = 9699691 = 347*27953
2*3*5*7*11*13*17*19*23 + 1 = 223092871 = 317*703763
2*3*5*7*11*13*17*19*23*29 + 1 = 6469693231 = 331*571*34231
2*3*5*7*11*13*17*19*23*29*31 + 1 = 200560490131, is prime
2*3*5*7*11*13*17*19*23*29*31*37 + 1 = 7420738134811 = 181*60611*676421
etc.