- Euclid's lemma
Euclid's lemma (Greek "polytonic|λῆμμα") is a generalization of Proposition 30 of Book VII of "
Euclid's Elements ". The lemma states that:If apositive integer divides the product of two other positive integers, and the first and second integers arecoprime , then the first integer divides the third integer.This can be written in notation::If "n"|"ab" and
gcd ("n","a") = 1 then "n"|"b".Proposition 30, also known as
Euclid 's firsttheorem , states::If aprime number divides the product of two positive integers, then the prime number divides at least one of the positive integers.That can be written as::If "p"|"ab" then "p"|"a" or "p"|"b".Often, proposition 30 is called Euclid's lemma instead of the generalization. A lemma is a "mini" theorem that is proven and used to prove a bigger theorem. Most of the time in mathematics textbooks Euclid's lemma is used to prove thefundamental theorem of arithmetic .Proof of Proposition 30
Say "p" is a prime factor of "ab", but also state that it is not a factor of "a". Therefore, , where "r" is the other corresponding factor to produce "ab".As "p" is prime, and also because it is not a factor of "a", "a" and "p" must be
coprime . This means that two integers "x" and "y" can be found so that (Bézout's identity ). Multiply with "b" on both sides::
:.
We stated previously that , and so:
:
:.
Therefore, "p" is a factor of "b". This means that "p" must always exactly divide either "a" or "b" or both.
Q.E.D. Example
Euclid's lemma in plain language says: If a number "N" is a multiple of a prime number "p", and "N" = "a" · "b", then at least one of "a" and "b" must be a multiple of "p". Say,
:,:,
and
:.
Then either
:
or
:.
Obviously, in this case, 7 divides 14 ("x" = 2).
ee also
*
Euclidean algorithm
*Fundamental theorem of arithmetic
Wikimedia Foundation. 2010.