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
Canonical name	EuclidsLemmaProof
Date of creation	2013-03-22 11:47:11
Last modified on	2013-03-22 11:47:11
Owner	akrowne (2)
Last modified by	akrowne (2)
Numerical id	9
Author	akrowne (2)
Entry type	Proof
Classification	msc 17B80
Classification	msc 81T30
Classification	msc 11A05
Classification	msc 81-00