Euclid s lemma

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 intergers 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

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.