alternative proof of Euclid’s lemma

We give an alternative proof (see Euclid’s lemma proof), which does not use the Fundamental Theorem of ArithmeticMathworldPlanetmath (since, usually, Euclid’s lemma is used to prove FTA).

Lemma 1.

If abc and gcd(a,b)=1 then ac.


By assumptionPlanetmathPlanetmath gcd(a,b)=1, thus we can use Bezout’s lemma to find integers x,y such that ax+by=1. Hence c(ax+by)=c and acx+bcy=c. Since aa and abc (by hypothesis), we conclude that aacx+bcy=c as claimed. ∎

Title alternative proof of Euclid’s lemma
Canonical name AlternativeProofOfEuclidsLemma
Date of creation 2013-03-22 14:12:27
Last modified on 2013-03-22 14:12:27
Owner alozano (2414)
Last modified by alozano (2414)
Numerical id 4
Author alozano (2414)
Entry type Proof
Classification msc 11A05