Euclid's theorem

Statement

There are infinitely many prime numbers. Equivalently, for each natural number $n$ there is a prime number $p$ with $p \ge n$.

Remarks

Euclid's proof: let $p_1, \dots, p_k$ be a finite list of primes, and let $N = p_1 p_2 \cdots p_k + 1$. A prime divisor of $N$ is not in the list, because each $p_i$ leaves the remainder $1$ when it divides $N$. The divergence of the sum of the reciprocals of the primes is a stronger result. Dirichlet's theorem on arithmetic progressions gives infinitely many primes in each suitable arithmetic progression.

History

The theorem is Proposition 20 of Book IX of the Elements of Euclid.

Explanations

L1 human

No finite list holds all the primes. Multiply all the primes of the list and add $1$. The new number leaves the remainder $1$ on division by each prime of the list, so its prime factors are new. For example, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$, and $59$ and $509$ are not in the list.