Euclid's proof
that there are an infinite number of primes
(by reductio ad absurdum)
Assume there are a finite number n of primes,
listed as [p_{1}, …, p_{n}].
Consider the
product of all the primes in the list, 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 (but not in the list of all primes),
or is divisible by another prime not in the list of all primes,
contradicting the assumption.