Lemma·L40
Euclid's lemma
If a prime divides a product, it divides one of the factors.
In words
If a prime number divides a product of two numbers, then it must divide at least one of the two factors.
Never needed: F05 · F10 · F13 · A02 · A03 · A04 · A05 · A07 (computed from the citation graph, not asserted).
Proof
- 1Assume . If we are done, so suppose ; we prove (excluded middle on ). Consider (Separation). is nonempty: (L12) is a multiple of , so (D030) and .
- 2By T09 let be the least element of (so ). Claim: divides every element of . Given , divide with (T10, ). Multiplying by and using distributivity, associativity and commutativity, . Now (as ) and (as ), hence (L19 (iv)); since , L19 (vi) gives . If then with , contradicting minimality; so and .
- 3
- 4If then , meaning (as : by D028 and commutativity with D027), contradicting . Hence .
- 5Finally we get . If then outright (L19 (iii)). If then (since by hypothesis), so by the claim, and gives . In all cases or .
∎
Remarks
Euclid's lemma is the multiplicative heart of the primes: it is precisely what fails for composite moduli (
but
divides neither
nor
), and it is the step that makes prime factorisation unique. The proof needs no gcd machinery, only well-ordering and the division algorithm: the least
with
must be
itself once
. With finite products available, an induction extends it to
for some
, and thence to the uniqueness half of the fundamental theorem of arithmetic.