---
tag: 0292EPPPT0
kind: statement
role: theorem
name: Euclid's theorem
aliases: [infinitude-of-primes]
msc: [11A41]
uses: [0SN0MAEKYX, 0SPBEDVNW1]
sources:
  - url: https://en.wikipedia.org/wiki/Euclid%27s_theorem
    locator: Euclid's proof
same_as:
  wikidata: Q1506253
  wikipedia: Euclid's theorem
---

## Statement

There are infinitely many [[prime numbers|0SN0MAEKYX]].
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|0SPBEDVNW1]] 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|00RA98X2CP]] is a stronger result.
[[Dirichlet's theorem on arithmetic progressions|0GNVN3CA2P]] 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.