# alternative proof of Euclid’s lemma

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

###### Lemma 1.

If $a\mid bc$ and $\gcd(a,b)=1$ then $a\mid c$.

###### Proof.

By assumption $\gcd(a,b)=1$, thus we can use Bezout’s lemma to find integers $x,y$ such that $ax+by=1$. Hence $c\cdot(ax+by)=c$ and $acx+bcy=c$. Since $a\mid a$ and $a\mid bc$ (by hypothesis), we conclude that $a\mid acx+bcy=c$ as claimed. ∎

Title alternative proof of Euclid’s lemma AlternativeProofOfEuclidsLemma 2013-03-22 14:12:27 2013-03-22 14:12:27 alozano (2414) alozano (2414) 4 alozano (2414) Proof msc 11A05