TheoremProved

Infinitude of primes (Euclid)

Statement

There are infinitely many prime numbers.

Why is it true?

If you ever had a complete finite list of all primes, multiplying them together and adding 1 gives a number none of them divides evenly — so that number must have some prime factor missing from the list, and the list could never have been complete.

Proof sketch

Given any finite list of primes $p_1,\dots,p_n$ , let $N=p_1p_2\cdots p_n+1$ . No $p_i$ divides $N$ (division by $p_i$ always leaves remainder $1$ ). By the fundamental theorem of arithmetic, $N$ has some prime factor $q$ ; since $q\ne p_i$ for every $i$ , $q$ is a prime missing from the original list. So no finite list can contain all primes.

Stated by

Euclid of Alexandria

Proved by

proved -300Euclid of Alexandria

Topics that use this theorem

Prime numbers The Riemann zeta function and the Riemann hypothesis Ancient Mathematics

Related theorems

Fundamental theorem of arithmetic Euler product formula for ζ(s)Bounded gaps between primes (Zhang, Maynard)

Step-by-step proofs

Euclid's proof that there are infinitely many primes

Euclid of Alexandria, -300

References

Euclid (trans. T. L. Heath) (1956). Euclid's Elements, Book IX, Proposition 20
G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers · DOI:10.1093/oso/9780199219858.001.0001