Euclid's proof of the infinitude of primes
We proceed by contradiction. Suppose there are in fact only finitely many prime numbers, . Let . Since leaves a remainder of 1 when divided by any of our prime numbers , it is not divisible by any of them. However, the Fundamental Theorem of Arithmetic states that all positive integers have a unique prime factorization. Therefore, must have a prime factor (possibly itself) that is not among our set of primes, . This means that does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.