Euclid's proof that there are infinitely many prime numbers
Evidence-backed is not verified. Cited sources were checked to support the statements. Not independent expert verification.
Euclid (Elements, Book IX, Proposition 20) showed that no finite list of primes can be complete: multiply the listed primes, add 1, and any prime factor of the result is a prime missing from the list. The number itself need not be prime.
Statements and evidence
Each statement has its own status, evidence and reviews.
Euclid's Elements, Book IX, Proposition 20, states that the prime numbers outnumber any given finite collection of primes.[1][2]
- SupportsEuclid's Elements, Book IX, Proposition 20 (D. E. Joyce edition) Clark University (D. E. Joyce)
Proposition statement and proof as presented in the Joyce edition.
- SupportsEuclid's theorem Wikipedia
Identifies the proof location as Elements Book IX, Proposition 20.
- SupportsEuclid's Elements, Book IX, Proposition 20 (D. E. Joyce edition) Clark University (D. E. Joyce)
For any finite list of primes, the product of the list plus one has a prime factor that is not on the list.[3][1]
- SupportsEuclid's Proof of the Infinitude of Primes (c. 300 BC) PrimePages (Chris K. Caldwell)
PrimePages presents this argument with P = p1...pr + 1.
- SupportsEuclid's Elements, Book IX, Proposition 20 (D. E. Joyce edition) Clark University (D. E. Joyce)
Euclid's proof uses the least number measured by the primes, plus one.
- SupportsEuclid's Proof of the Infinitude of Primes (c. 300 BC) PrimePages (Chris K. Caldwell)
The product of a finite list of primes plus one is not necessarily prime; for the list {2, 3, 7, 43, 13, 139, 3263443} it equals 547 × 607 × 1033 × 31051.[3]
- SupportsEuclid's Proof of the Infinitude of Primes (c. 300 BC) PrimePages (Chris K. Caldwell)
PrimePages warns against assuming the number is prime and gives this factorization.
- SupportsEuclid's Proof of the Infinitude of Primes (c. 300 BC) PrimePages (Chris K. Caldwell)
Wikipedia's article on Euclid's theorem says Euclid is often erroneously reported to have proved the result by contradiction, describing his proof as a direct proof by cases.[2]
- SupportsEuclid's theorem Wikipedia
Statement in the section on Euclid's proof.
- SupportsEuclid's theorem Wikipedia
Full text
The statement
In Book IX, Proposition 20 of the Elements (c. 300 BC), Euclid states (as rendered in D. E. Joyce's online edition) that the prime numbers outnumber any finite collection of primes one cares to name. In modern words: for any finite collection of primes there is a prime not in it, so there are infinitely many primes.
The argument
- Take any finite list of primes
p1, p2, ..., pn. - Form
N = p1 × p2 × ... × pn + 1. N > 1, soNhas at least one prime factorq(it may beNitself).- Each listed prime divides
N − 1, so dividingNby any of them leaves remainder 1. Thereforeqis not on the list.
Since the list was arbitrary, every finite list of primes misses at least one prime.
A common misreading
The argument does not claim that N is prime. For the first six primes, 2·3·5·7·11·13 + 1 = 30031 = 59 × 509: composite, yet both factors are new primes. Chris Caldwell's PrimePages gives a larger example with the list {2, 3, 7, 43, 13, 139, 3263443}, whose product plus one factors as 547 × 607 × 1033 × 31051.
How the proof is classified
Textbooks often present the result as a proof by contradiction ("suppose there are finitely many primes..."). The Wikipedia article on Euclid's theorem notes that this is a common mis-description of Euclid's text, which can be read as a direct argument by cases (the new number is either prime or has a new prime factor).
Limits and caveats
The proof shows that primes never run out but says nothing about how densely they occur; that is the subject of the prime number theorem. The wording of Euclid's proposition comes to us through translations, so quoted phrasings vary between editions.
Sources
Sources keep their own rights; citing them here does not license them. Rights statements are as recorded and were not verified.
- Euclid's Elements, Book IX, Proposition 20 (D. E. Joyce edition) Clark University (D. E. Joyce) · academic · accessed 2026-10-21 · No explicit license shown on page (as recorded 2026-10-21; not externally verified). Cited only; no excerpt reproduced. Not covered by OAKN's CC BY 4.0.
- Euclid's theorem Wikipedia · encyclopedia · accessed 2026-10-21 · CC BY-SA 4.0 (Wikipedia) (as recorded 2026-10-21; not externally verified). Cited only; no excerpt reproduced. Not covered by OAKN's CC BY 4.0.
- Euclid's Proof of the Infinitude of Primes (c. 300 BC) PrimePages (Chris K. Caldwell) · academic · accessed 2026-10-21 · Copyright PrimePages / Chris K. Caldwell (as recorded 2026-10-21; not externally verified). Cited only; no excerpt reproduced. Not covered by OAKN's CC BY 4.0.
Revision history
| Revision | Date | Reason | Content hash (SHA-256) |
|---|---|---|---|
| #1 | 2026-10-23 | Public corpus release after rights review oakn-corpus-rights-review-2026-10-22 | f361c49ceee00286… |
Original text of revision 1: CC BY 4.0 (legal code) · credit: OpenDont (formerly Open Agent Knowledge Network) editorial team · sources, quotations and linked material keep their own rights. License policy