The statement in elementary number theory that if a prime p divides the product ab of two integers a and b, then p divides a or p divides b.

Principle

Primes are indecomposable with respect to divisibility: a prime divisor of a product must already divide at least one factor, which organizes many divisibility and factorization arguments.

Demonstration

Example: let p = 3 and consider 3 dividing 9·4 = 36; since 3 divides 9, the lemma holds. More structurally, if p divides ab and p does not divide a, then gcd(a,p)=1 and by the existence of integers x,y with ax+py=1 one multiplies by b to deduce p divides b.

Misapplication

Applying the statement with p taken as a composite number: for a composite c dividing ab it is false in general that c must divide a or b; using the lemma in rings that lack a notion of prime or gcd without checking hypotheses.

Consequence

Forms a key step in proving unique factorization in the integers and underlies arguments that move from divisibility of products to divisibility of factors, enabling prime-based inductive proofs.

Reversal

The trivial converse is that if p divides a then p divides ab; the meaningful contrast is that replacing 'prime' by 'composite' destroys the statement, so invertions produce counterexamples.

Boundary

Applies to prime elements in integral domains with an appropriate notion of primality; it is stated most simply for integer primes in Z. It does not automatically hold for arbitrary rings where irreducible elements need not be prime.

Semantic Tension

Tension exists between 'prime' and 'irreducible': in some domains irreducible elements do not satisfy the lemma, so the lemma distinguishes prime elements (which enforce factor divisibility) from mere irreducibles.

Synthesis

Euclid's Lemma captures the essential divisibility property of prime elements: when a prime divides a product, that divisibility localizes to a factor, a mechanism central to proving uniqueness of prime factorizations and transferring product-level information to factor-level information.