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.