Famous Theorems of Mathematics/Euclid's proof of the infinitude of primes

The Greek mathematician Euclid gave the following elegant proof that there are an infinite number of primes. It relies on the fact that all non-prime numbers --- composites --- have a factorization into primes.

Euclid's proof shows that for any finite set S of prime numbers, one can find a prime not belonging to that set. (Contrary to what is asserted in many books, this need not be the first n prime numbers for some n, nor did Euclid assume it to be the set of all prime numbers. For example, the finite set could be { 2, 7, 31 }.)

Euclid considered the number ΠS, the result of multiplying all members of the finite set S. (For example, if S is { 2, 7, 31 } then ΠS is 2 × 7 × 31 = 434.) Then he added 1 to this number, getting 1 + ΠS. (For example, if S is { 2, 7, 31 } then 1 + ΠS is 1 + (2 × 7 × 31) = 435.) Euclid claimed that this number 1 + ΠS cannot be divisible by any of the primes in the finite set S that we started with. (For example, if S is { 2, 7, 31 } then the number 1 + ΠS, which is 1 + (2 × 7 × 31) = 435, is not divisible by 2, 7, or 31; in fact it is 435 = 3 × 5 × 29.) But 1 + ΠS, like every number, must either be prime itself or be divisible by some prime number other than itself. Either way we have a prime number that is not in our initial finite set S. (For example, if S is { 2, 7, 31 } then the resulting new prime numbers not in S are 3, 5, and 29.)

In Euclid's phrasing of the proof, rather than multiplying all of the primes in S, the smallest common multiple was considered. But the smallest common multiple of distinct prime numbers is the same as their product.

Many books erroneously state that Euclid's proof was by contradiction, starting with the assumption that only finitely many prime numbers exist.