Euclid's proof of the infinitude of primes
This is proved by contradiction. Suppose there is a finite number of primes and let them be . Let . Then we have . When divided by any of the primes , leaves a remainder of 1 implying that either is prime or that it has some other prime factors not in the set . In any case we have it so that does not contain all prime numbers. Contradiction!