# 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.

Title Euclid’s lemma proof EuclidsLemmaProof 2013-03-22 11:47:11 2013-03-22 11:47:11 akrowne (2) akrowne (2) 9 akrowne (2) Proof msc 17B80 msc 81T30 msc 11A05 msc 81-00