Euclid's lemma is a generalisation of Proposition 30 of Book VII of Euclid's Elements. The lemma states that

If a positive integer divides the product of two other positive integers, and the first and second integers are coprime, then the first integer divides the third integer.

This can be written in notation:

If a|bc and gcd(a,b)=1 then a|c.

Proposition 30 states:

If a prime number divides the product of two positive integers, then the prime number divides at least one of the positive integers.

If p|bc then p|b or p|c.

See also

• Euclid
• Euclidean algorithm
• Fundamental theorem of arithmetic