Euclid's proof of the infinitude of primes
Euclid's proof of the infinitude of primes is a proof by Euclid that the number of prime numbers is infinite.
Proof
We proceed by contradiction. Suppose there are only finitely many prime numbers; let's call them . Let
. When
is divided by any of our primes
it leaves a remainder of 1, so none of these primes divide
. Since every positive integer has at least one prime factor,
has some prime factor (possibly itself) not in the set
. Thus
does not contain all prime numbers. Contradiction! Our original assumption must have been false, so there are in fact infinitely many primes.