Euclid's proof that there are infinitely many primes

---

Suppose that there is a largest prime. Then we can list them, like this: p₁, p₂, p₃, ..., p_N. Consider the number

Q = p₁, p₂, p₃, ..., p_N + 1.

If Q is prime, then we have found a prime larger than the largest prime p_N. If Q is not prime, then it has a prime divisor p. This divisor must be one of the p_i. But then it leaves a remainder of 1 when divided into Q. Again we arrive at a contradiction. Thus the assumption that there is a largest prime is false. That is, there are infinitely many primes.

Historical notes

The statement that there are infinitely many primes is Proposition 20 of Book IX of Euclid's Elements. See Sir Thomas Heath, p. 412 of Euclid, the thirteen books of the Elements, volume II, Dover Publications, 1956.

Another proof

Recall that n! is the product of the numbers 1, 2, 3, ..., n. Let p be the smallest prime factor of n. If p <= n then p is one of the integers 2, 3, 5, ..., n. But then, when divided into n! + 1 it leaves a remainder of one, and so cannot be a factor. Therefore p > n. Q.E.D.