# Euclid's Theorem

I came across this beautiful proof in GEB and wanted to reproduce it here.

#### Proof that there are infinitely many primes:

Assume there are finitely many primes. Let’s denote the finite set of all primes by \(P = \{p_1, p_2, ..., p_n\}\).

Consider the number \(x=1+\prod ^{n}_{i=1} p_i\).

\(x\) has a remainder of \(1\) for all primes \(p_i\) in \(P\) (and therefore is not divisible by any of them). Therefore, the prime factorization of \(x\) includes primes not in the set \(P\).

However, we stated that \(P\) was the set of *all* primes. Finding a
prime outside of that set is a contraction of our assumption.
Therefore, our assumption is false.