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\mathrm{\mid }bc$ and $\gcd \mathit{}\mathrm{(}a\mathrm{,}b\mathrm{)}\mathrm{=}\mathrm{1}$ then $a\mathrm{\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.∎