Euclid's Proof of the Infinitude of Primes

In today's blog, I will present a very well known proof. What makes this proof especially appealing is that it is not too complex. Even so, it is very powerful. This theorem was first presented in Euclid's Elements (Book IX, Proposition 20).

Theorem: There are an infinite number of primes.

Proof:

(1) Assume that there is only a finite number of primes.

(2) Then, there exists a prime p_n that is the largest prime.

(3) Let p₁, p₂, ..., p_n be the list of all primes that exist.

(4) Let x = p₁*p₂*...*p_n + 1.

(5) By the fundamental theorem of arithmetic (see Theorem 3, here), we know there is at least one prime that divides x. Let us call this prime p*.

(6) But none of the primes p₁ ... p_n divide x since x ≡ 1 (mod p_i) for any of the primes p₁ ... p_n

(7) Therefore, we have a contradiction. We have a prime p* that is not in the complete list of primes.

(8) So, we reject our assumption in step#1 and conclude that there are an infinite number of primes that exist.

QED