Euclid’s lemma proof

We have $a|bc$ , so $bc=na$ , with $n$ an integer. Dividing both sides by $a$ , we have

\frac{bc}{a}=n

But $\gcd(a,b)=1$ implies $b/a$ is only an integer if $a=1$ . So

\frac{bc}{a}=b\frac{c}{a}=n

which means $a$ must divide $c$ .

Note that this proof relies on the Fundamental Theorem of Arithmetic. The alternative proof of Euclid’s lemma avoids this.