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

Consider the number .

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

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