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\\mid bc$ and $\\gcd(a,b)=1$ then $a\\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.∎

单词	AlternativeProofOfEuclidsLemma
释义	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\\mid bc$ and $\\gcd(a,b)=1$ then $a\\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.∎
随便看	singular function SingularMeasure singular measure SingularSet singular set SingularSolution singular solution SingularValueDecomposition singular value decomposition Sinusoid sinusoid SixExponentialsTheorem six exponentials theorem SizeofAGraph size (of a graph) SizeOfMaximalIndependentSetAndChromaticNumber size of maximal independent set and chromatic number SkewDerivation skew derivation SkewesNumber Skewes’ number SkewHadamardMatrix skew Hadamard matrix SkewHermitianMatrix skew-Hermitian matrix