Euclid’s lemma proof


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

bca=n

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

bca=bca=n

which means a must divide c.

Note that this proof relies on the Fundamental Theorem of ArithmeticMathworldPlanetmath. 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