Euclid's lemma is a basic but powerful statement in elementary number theory about divisibility by prime numbers. In its usual modern form it says: if p is a prime and p divides a product ab of integers, then p divides a or p divides b. This property is essential for establishing unique factorization of integers and for many elementary proofs in arithmetic.

Statement and equivalent form

The lemma is commonly expressed two equivalent ways: prime-divides-product — if p is prime and p|ab then p|a or p|b — and the coprime version — if p|ab and gcd(p,a)=1 then p|b. Both formulations are used depending on the context. Note that this is distinct from the "division lemma" or division algorithm, which asserts that given integers a and b>0 there exist unique q and r with a=bq+r and 0≤r<b.

Proof sketch

A short classical proof uses the property of greatest common divisors. If p divides ab but not a, then gcd(a,p)=1. By Bézout's identity there exist integers x and y with ax+py=1. Multiplying by b gives abx+pby=b. Since p divides abx and p divides pby, p divides the right-hand side b. Therefore p divides b. This elementary argument avoids deeper factorization facts.

Examples and contrasts

  • Example: p=3 divides 3·20 = 60, and indeed 3 divides 3 (or any factor containing 3).
  • Contrast: the property fails for composite divisors. For instance 6 divides 2·3 but 6 divides neither 2 nor 3.

History, importance and uses

The result is attributed to Euclid and appears in Book VII of his Elements, where it plays a role in arguments about divisibility and primes. Modern presentations call it Euclid's lemma or Euclid's first theorem; historical discussion and editions can be found in many introductions to number theory and classical sources on Euclid and on the lemma. It is a central ingredient in the usual proof of the fundamental theorem of arithmetic (unique factorization of integers) and is used to show, for example, the infinitude of primes and properties of rational numbers.

Analogues of Euclid's lemma appear in abstract algebra: in an integral domain an element p is called prime if p divides a product implies p divides a factor. In unique factorization domains (UFDs) prime elements and irreducible elements coincide, and a version of Euclid's lemma holds. For further background on related lemmas and formal definitions see standard texts and online references about lemmas and on number-theoretic foundations.