# Euclid's lemma

**Euclid's lemma** is the statement of elementary number theory that if a prime number p divides a product of two integers, then p divides at least one of the factors: if p | ab, then p | a or p | b.<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup> It appears as [Proposition](https://www.edgepedia.org/proposition) 30 of Book VII of Euclid's *Elements* (circa 300 BC), phrased in the language of measuring: "If two numbers by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers."<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup><sup> • </sup><sup>[2](https://proofwiki.org/wiki/Euclid%27s_Lemma_for_Prime_Divisors/Proof_3)</sup>

| Key fact | Detail |
|---|---|
| Statement | If p is prime and p \| ab for integers a, b, then p \| a or p \| b<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup> |
| Classical source | Proposition 30, Book VII of Euclid's *Elements*<sup>[2](https://proofwiki.org/wiki/Euclid%27s_Lemma_for_Prime_Divisors/Proof_3)</sup> |
| Characterizing property | The property holds for primes and fails for every composite number; for example 6 divides 15 · 14 but divides neither 15 nor 14<sup>[3](https://www.math.brown.edu/~jhs/MA0076/IHM2020NumberTheoryUnit4.pdf)</sup> |
| Multi-factor form | If p divides a product a₁a₂⋯aₙ, then p divides at least one factor, proved by induction on n<sup>[4](https://sites.millersville.edu/bikenaga/number-theory/fundamental-theorem/fundamental-theorem.html)</sup> |
| Main use | The key step in proving uniqueness of prime factorization (the Fundamental Theorem of Arithmetic)<sup>[5](https://www.maths.tcd.ie/pub/Maths/Courseware/NumberTheory/Stein.pdf)</sup> |
| Historical note | Euclid proved the lemma but never stated the full uniqueness theorem; Gauss first stated uniqueness explicitly in 1801 and deduced it from VII.30<sup>[6](https://www.math.umd.edu/~pbrosnan/notes/ugalg/sect0004.html)</sup><sup> • </sup><sup>[7](https://calteches.library.caltech.edu/3832/)</sup> |
| Algebraic scope | The property defines prime elements in an integral domain; it fails for some irreducible elements, for example 2 in ℤ[√−5]<sup>[8](https://www.math.ucla.edu/~sharifi/notes/algebra-ch05.html)</sup> |

## Euclid's proof

Euclid's argument is a proof by [contraposition](https://www.edgepedia.org/contraposition) built on three earlier propositions of Book VII.<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup> Suppose a prime number d divides the product ab but does not divide a. By Proposition VII.29, a prime that does not measure a number is relatively prime to it, so d and a are coprime.<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup><sup> • </sup><sup>[2](https://proofwiki.org/wiki/Euclid%27s_Lemma_for_Prime_Divisors/Proof_3)</sup> Let e be the number ab/d, so that d · e = a · b. Proposition VII.19 then gives the ratio d : a = b : e. Since d and a are relatively prime, their ratio is in lowest terms (VII.21), and Proposition VII.20 says that numbers in the same ratio as a pair in lowest terms are measured the same number of times, the greater the greater and the less the less. It follows that d divides b. The symmetric argument shows that if d does not divide b, it divides a, so in every case d divides one of the two factors.<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup>

The proof relies on the theory of ratios of whole numbers rather than on the [Euclidean algorithm](https://www.edgepedia.org/euclidean-algorithm) or [Bézout's identity](https://www.edgepedia.org/bezouts-identity), which modern textbooks usually use instead.<sup>[2](https://proofwiki.org/wiki/Euclid%27s_Lemma_for_Prime_Divisors/Proof_3)</sup>

## Modern proofs

**The gcd route.** Most current textbooks prove the lemma from properties of the greatest common divisor. If p is prime and p does not divide a, then gcd(p, a) = 1, since the only positive divisors of p are 1 and p. One standard argument uses the identity gcd(an, bn) = gcd(a, b) · |n|, proved by stepping through the Euclidean algorithm: since p divides both pb and ab, it divides gcd(pb, ab) = b · gcd(p, a) = b.<sup>[5](https://www.maths.tcd.ie/pub/Maths/Courseware/NumberTheory/Stein.pdf)</sup> An equivalent route uses Bézout's identity, which expresses the gcd as a linear combination: writing 1 = px + ab y, multiplying by b gives b = pbx + aby, and since p divides both terms on the right, p divides b.<sup>[3](https://www.math.brown.edu/~jhs/MA0076/IHM2020NumberTheoryUnit4.pdf)</sup>

**A proof without gcds.** The lemma also admits proofs that avoid the gcd machinery entirely. One argument uses double induction, first on the prime p and then on the product xy, reducing the problem through remainders x = pqₓ + rₓ with 0 ≤ rₓ < p until the base cases are reached.<sup>[9](https://webdocs.cs.ualberta.ca/~hayward/272/jem/euclem.pdf)</sup> A proof of this kind, attributed to [Ernst Zermelo](https://www.edgepedia.org/ernst-zermelo) (1871–1953), who discovered it around 1900 and published it in 1934, appears in textbooks under headings such as "uniqueness without Euclid's lemma".<sup>[6](https://www.math.umd.edu/~pbrosnan/notes/ugalg/sect0004.html)</sup>

## Role in the Fundamental Theorem of Arithmetic

The lemma is the engine behind the uniqueness half of the Fundamental Theorem of Arithmetic, which says that every integer greater than 1 factors into primes in essentially one way.<sup>[5](https://www.maths.tcd.ie/pub/Maths/Courseware/NumberTheory/Stein.pdf)</sup> The existence of a factorization is proved by strong induction and does not need the lemma; uniqueness does. If two factorizations p₁^{m₁}⋯pⱼ^{mⱼ} = q₁^{n₁}⋯qₖ^{nₖ} exist, the lemma (in its multi-factor form) shows that p₁ divides some qᵢ, and since both are prime, p₁ = qᵢ; canceling and repeating proves that the factorizations match.<sup>[4](https://sites.millersville.edu/bikenaga/number-theory/fundamental-theorem/fundamental-theorem.html)</sup>

The multi-factor form itself follows from the two-factor form by induction: grouping the product as (a₁a₂⋯aₙ₋₁) · aₙ, the prime divides one of the two pieces, and induction finishes the argument.<sup>[4](https://sites.millersville.edu/bikenaga/number-theory/fundamental-theorem/fundamental-theorem.html)</sup><sup> • </sup><sup>[3](https://www.math.brown.edu/~jhs/MA0076/IHM2020NumberTheoryUnit4.pdf)</sup>

Euclid himself never stated the uniqueness theorem. The closest he came is Proposition 14 of Book IX, which says that the smallest positive integer divisible by primes p₁, …, p_r is not divisible by any other primes. The full Fundamental Theorem of Arithmetic was apparently first stated by Kama al Din al-Farisi (1267–1319), and Gauss gave a proof of uniqueness in Article 16 of his *Disquisitiones Arithmeticae*, noting that by Euclid's lemma the set of primes in any two factorizations of the same integer must be the same, with only the exponents possibly differing.<sup>[6](https://www.math.umd.edu/~pbrosnan/notes/ugalg/sect0004.html)</sup> A Caltech historical account summarizes the point: the existence of prime factorization was known in Euclid's time, but uniqueness was first explicitly stated by Gauss in 1801, deduced from Proposition VII.30.<sup>[7](https://calteches.library.caltech.edu/3832/)</sup>

## Why the lemma characterizes primes

The divisibility property is a special feature of prime numbers. If c is composite, write c = ab with neither factor equal to c; then c divides the product ab but divides neither a nor b, so no composite number has the property.<sup>[1](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)</sup> A concrete example: 6 divides 15 · 14 = 210, but 6 divides neither 15 nor 14.<sup>[3](https://www.math.brown.edu/~jhs/MA0076/IHM2020NumberTheoryUnit4.pdf)</sup>

A probabilistic result underlines how special the property is: a randomly chosen implication of the form "r | ab implies r | a or r | b" is almost surely false, with an asymptotic formula quantifying how quickly the failures accumulate.<sup>[10](https://arxiv.org/abs/1602.03555)</sup>

## Generalization to rings

In abstract algebra the lemma becomes the definition of a prime element: an element p of an integral domain is prime if p | ab implies p | a or p | b, equivalently if the principal ideal (p) is a prime ideal.<sup>[11](https://citeseerx.ist.psu.edu/document?doi=3ea80cfa51180cca0e7cf50244bbb6160ceae860&repid=rep1&type=pdf)</sup><sup> • </sup><sup>[12](https://crypto.stanford.edu/pbc/notes/commalg/factorization.html)</sup> In any integral domain, every prime element is irreducible, but the converse fails in general, and the failure is exactly the failure of Euclid's lemma.<sup>[12](https://crypto.stanford.edu/pbc/notes/commalg/factorization.html)</sup><sup> • </sup><sup>[8](https://www.math.ucla.edu/~sharifi/notes/algebra-ch05.html)</sup>

The standard counterexample is the ring ℤ[√−5]. There the element 2 is irreducible, yet

\[ 6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}), \]

and 2 divides neither 1 + √−5 nor 1 − √−5, so 2 is not prime and Euclid's lemma fails for it.<sup>[8](https://www.math.ucla.edu/~sharifi/notes/algebra-ch05.html)</sup><sup> • </sup><sup>[12](https://crypto.stanford.edu/pbc/notes/commalg/factorization.html)</sup> This same ring fails to be a unique factorization domain, which reflects the general equivalence: a domain in which every nonzero nonunit has a factorization is a unique factorization domain precisely when every irreducible element is prime, that is, when Euclid's lemma holds for all irreducibles.<sup>[8](https://www.math.ucla.edu/~sharifi/notes/algebra-ch05.html)</sup><sup> • </sup><sup>[12](https://crypto.stanford.edu/pbc/notes/commalg/factorization.html)</sup> In a principal ideal domain, irreducible elements are always prime, which is the analog of Euclid's lemma and the reason every PID is a UFD.<sup>[8](https://www.math.ucla.edu/~sharifi/notes/algebra-ch05.html)</sup><sup> • </sup><sup>[13](https://math.hodapp.com/lectures/foundations/rings/factorization-domains.html)</sup>

## References

1. [Euclid's Elements, Book VII, Proposition 30 (with guide and proof outline)](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII30/)
2. [Euclid's Lemma for Prime Divisors/Proof 3, ProofWiki](https://proofwiki.org/wiki/Euclid%27s_Lemma_for_Prime_Divisors/Proof_3)
3. [J. Silverman, Introduction to Higher Mathematics, Number Theory Unit 4](https://www.math.brown.edu/~jhs/MA0076/IHM2020NumberTheoryUnit4.pdf)
4. [The Fundamental Theorem of Arithmetic, Millersville University notes (Bikenaga)](https://sites.millersville.edu/bikenaga/number-theory/fundamental-theorem/fundamental-theorem.html)
5. [W. Stein, Elementary Number Theory, Chapter 1 (Theorem 1.1.19)](https://www.maths.tcd.ie/pub/Maths/Courseware/NumberTheory/Stein.pdf)
6. [P. Brosnan, Undergraduate Algebra: Attempt at getting the history right, UMD](https://www.math.umd.edu/~pbrosnan/notes/ugalg/sect0004.html)
7. [A Centennial History of the Prime Number Theorem, Caltech Engineering & Science](https://calteches.library.caltech.edu/3832/)
8. [R. Sharifi, Abstract Algebra, Chapter 5: Advanced ring theory, UCLA](https://www.math.ucla.edu/~sharifi/notes/algebra-ch05.html)
9. [Euclid's little lemma: book 7 proposition 30, University of Alberta course notes](https://webdocs.cs.ualberta.ca/~hayward/272/jem/euclem.pdf)
10. [On the Success of Mishandling Euclid's Lemma, arXiv:1602.03555](https://arxiv.org/abs/1602.03555)
11. [Commutative Algebra (course notes, CiteSeerX), section on EL-domains](https://citeseerx.ist.psu.edu/document?doi=3ea80cfa51180cca0e7cf50244bbb6160ceae860&repid=rep1&type=pdf)
12. [Factorization, Stanford commutative algebra notes (P. B. Cohen)](https://crypto.stanford.edu/pbc/notes/commalg/factorization.html)
13. [Factorization domains: UFD, PID, Euclidean, Math foundations lectures](https://math.hodapp.com/lectures/foundations/rings/factorization-domains.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Divisibility, GCD, and the integers*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license