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 $p_1, p_2, p_3, \ldots, p_n$ . Let $x=p_1\cdot p_2\cdot p_3 \cdots p_n + 1$ . When $x$ is divided by any of our primes $p_1, p_2, p_3, \ldots, p_n$ it leaves a remainder of 1, so none of these primes divide $x$ . Since every positive integer has at least one prime factor, $x$ has some prime factor (possibly itself) not in the set $\{ p_1,p_2,p_3,\ldots,p_n\}$ . Thus $\{ p_1,p_2,p_3,\ldots, p_n\}$ does not contain all prime numbers. Contradiction! Our original assumption must have been false, so there are in fact infinitely many primes.

Page

Toolbox

Search

Euclid's proof of the infinitude of primes

Proof

See Also