Euclid's Theorem

Theorem

For any finite set of prime numbers, there exists a prime number not in that set.

Corollary

There are infinitely many prime numbers.

Proof by Contradiction

Let $\mathbb P$ be a finite set of prime numbers.

Consider the number: $\displaystyle n_p = \left({\prod_{p \in \mathbb P} p}\right) + 1$.

Take any $p_j \in \mathbb P$.

We have that $\displaystyle p_j \backslash \prod_{p \in \mathbb P} p$.

Hence $\displaystyle \exists q \in \Z: \prod_{p \in \mathbb P} p = q p_j$.

So:

	\(\displaystyle \)	\(\displaystyle n_p\)	\(=\)	\(\displaystyle q p_j + 1\)	\(\displaystyle \)	by Division Theorem
	\(\displaystyle \implies\)	\(\displaystyle n_p\)	\(\perp\)	\(\displaystyle p_j\)	\(\displaystyle \)	by definition of coprime

So $p_j \nmid n_p$.

There are two possibilities:

• $n_p$ is prime, which is not in $\mathbb P$.

• $n_p$ is composite. But from Positive Integer Greater than 1 has a Prime Divisor‎, it must be divisible by some prime.

That means it is divisible by a prime which is not in $\mathbb P$.

So in either case there exists at least one prime which is not in the original set we created.

Hence the result.

$\blacksquare$

Proof of Corollary

Assume that there are only finitely many prime numbers, and that there is a grand total of $n$ primes.

Then it is possible to define the set of all primes: $\mathbb P = \left\{{p_1, p_2, \ldots, p_n}\right\}$.

From the main proof, however, we can always create a prime which is not in $\mathbb P$.

So we can never create a finite list of all the primes, because we can guarantee to construct a number which has prime factors that are not in this list.

Thus, there are infinitely many prime numbers.

$\blacksquare$

Euclid Number

During the course of the proof of the corollary, we assume that all the primes (of our supposedly finite set) are multiplied together, and $1$ added. The resulting number is then either a prime or contains a prime factor not on that original list.

Such a number is known as a Euclid number.

Although this is not quite the way Euclid originally stated his original theorem, it is such a well-known and accessible proof that it is considered to have entered the mainstream of "general knowledge".

Fallacy

There is a danger in the proof of the corollary.

It is often seen to be stated that: the number made by multiplying all the primes together and adding $1$ is not divisible by any members of that set, so it is not divisible by any primes and "is therefore itself prime".

Sometimes readers think that if $P$ is the product of the first $n$ primes then $P + 1$ is itself prime.

This is not the case. For example:

$\left({2 \times 3 \times 5 \times 7 \times 11 \times 13}\right) + 1 = 30\ 031 = 59 \times 509$

both of which are prime, but, take note, not in that list of six primes that were multiplied together to get $30\ 030$ in the first place.

Historical Note

This is Proposition 20 of Book IX of Euclid's The Elements.

See Also

• Furstenberg's Proof of the Infinitude of Primes

Sources

• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.13$: Theorem $23$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 22 \beta, \ \S 22 \gamma$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $2.15$
• George F. Simmons: Calculus Gems (1992): Chapter $\text{B}.16$: Theorem $2$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.12$: Proposition $1.12.2$