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

Title	alternative proof of Euclid’s lemma
Canonical name	AlternativeProofOfEuclidsLemma
Date of creation	2013-03-22 14:12:27
Last modified on	2013-03-22 14:12:27
Owner	alozano (2414)
Last modified by	alozano (2414)
Numerical id	4
Author	alozano (2414)
Entry type	Proof
Classification	msc 11A05