# Euclid's Lemma $\,(a,b)=1,\ a\mid bc\Rightarrow a\mid c\,$ in Bezout, gcd, ideal form

Let $$A$$ be a UFD, e.g. $$A = \Bbb Z$$ or $$\,\Bbb Q[x,y]$$. Assume $$a,b \in A$$ are relatively prime, $$c \in A$$ and $$a | bc$$. To prove that $$a|c$$, is the following approach correct (or do you have to use some type of prime factorization argument)?

By the relatively prime assumption, $$\gcd(a,b)$$ is a unit. Call that unit $$u \in A^{\times}$$. Then we can write $$u = ax + by$$ for some $$x,y \in A$$. But then, $$c = c \cdot u = c(ax+by)=cax+cby$$. However, it is clear that $$a|cax$$ and the fact that $$a|bc$$ implies $$a|cby$$. Thus, $$a|cax+cby=c$$.

• I edited the title to make it more descriptive. Please feel free modify it as you wish. Commented Dec 7, 2012 at 3:19
• @Bill Is the new title really that descriptive of the question, or more aimed at the accepted answer? With a related query even if I find this post, I may stop upon reading the specifics of the posted question. I think your answer is extremely useful, would it make sense to create a community wiki, with a more general scope, to be more easily accessed and spotted, as is suggested in the most upvoted comment at abstract duplicates? Commented Apr 23, 2023 at 19:51

No, we can't use a Bezout equation from the extended Euclidean algorithm since UFDs need not be Euclidean / PID, e.g. in $$\rm\,\Bbb Q[x,y],\,$$ $$\rm\,gcd(x,y) = 1\,$$ but $$\rm\, x\:\! f + y\:\! g = 1\,\Rightarrow\, 0 = 1\,$$ by eval at $$\rm\,x,y=0.$$

Below are $$\:\!3\:\!$$ proofs, using $$(0)$$ inductive extension of the simple Euclid's Lemma (case $$\,a\,$$ prime), $$(1)$$ gcd Distributive Law, and $$(2)$$ existence and uniqueness of prime factorizations.

$$(0)\ \:\!$$ We induct on the number $$\:\!k\:\!$$ of prime factors of $$\,a,\,$$ using as inductive step  Euclid's Lemma$$_{\,p}\,$$ (if a prime divides a product then it divides some factor). If $$\,k=0\,$$ then $$\,a\,$$ is a unit so $$\,a\mid c.\,$$ Else $$\,a = p\bar a\,$$ for a prime $$\,p\,$$ so $$\,p\bar a\mid bc\,\Rightarrow\,p\mid b\,$$ or $$\,p\mid c,\,$$ so $$\,\color{#c00}{p\mid c}\,$$ by $$\,(p,b)=1\,$$ by $$\,(p\bar a,b)=1$$. Cancelling $$\,p\,$$ from $$\,p\bar a\mid bc\Rightarrow \bar a\mid b\,\color{#c00}{c/p},\,$$ and $$\,(\bar a,b)=1\,$$ by $$\,(p\bar a,b)=1.\,$$ Notice $$\,\bar a\,$$ has fewer prime factors than $$\,a=p\bar a,\,$$ thus $$\,\bar a\mid \color{#c00}{c/p}\underset{\times\, p}\Rightarrow p\bar a\mid c\$$ (i.e. $$\,a\mid c),\,$$ by induction.

$$(1)\$$ By gcds: $$\rm\ a\mid ac,bc\Rightarrow a\mid \color{0A0}{(ac,bc)\!\:{\overset{\rm\color{#c00}{DL}}=(\underbrace{a,b}_{ \approx\, 1}})c^{\phantom{|^{|^|}}}}\!\!\!\Rightarrow a\mid c,\,$$ by $$\rm\color{#c00}{DL}=$$ gcd Distributive Law

$$(2)$$ $$\rm\ a\mid bc\:$$ so $$\rm\:ad = bc\:$$ for some $$\rm\:d.\:$$ By existence, we can factor all four terms into prime factors. By uniqueness, the same multiset of primes occurs on both sides (up to unit factors / associates). So all of the primes in the factorization of $$\rm\:a\:$$ must also occur on the RHS, necessarily in the factorization of $$\rm\:c,\:$$ since, by hypothesis, $$\rm\:a,b\:$$ are coprime, hence share no prime factors. Therefore $$\rm\:a\mid c\:$$ since all of its prime factors (counting multiplicity) occur in $$\rm\:c.\:$$ Note that this inference can be expressed purely multiset-theoretically: $$\rm\: A\cap B = \{\,\},\ \ A \cup D\,=\, B\cup C\:$$ $$\Rightarrow$$ $$\rm\:A\subset C,\:$$ where $$\rm\:C =$$ multiset of primes in the unique prime factorization of $$\rm\:c,\:$$ and similarly for $$\rm\:A,B,D\,$$ (here we're essentially ignoring units by replacing "equal" by "associate" or, equivalently, by working in the reduced multiplicative monoid obtained by factoring out the unit group).

Remark  Specializing $$\rm\,a\,$$ prime above shows irreducibles are prime in a UFD or GCD domain.

Below we show how the common $$\rm\color{#0a0}{Bezout}$$-based proof of  Euclid's Lemma in $$\,\Bbb Z\,$$ is a special case of $$(1),\,$$ by successively translating it into the language of gcds and ideals.

Euclid's Lemma in $$\rm\color{#0a0}{Bezout}$$, $$\rm\color{#90f}{gcd}$$ and ideal form

{\!\begin{align} \color{#0a0}{ax\!+\!by}=&\,\color{#c00}{\bf 1},\,\ a\ \mid\ bc\ \ \Rightarrow\ a\ \mid\ c.\ \ \ {\bf Pf}\!:\ a\ \mid\,\ ac,\ bc\, \Rightarrow\, a\,\mid acx\!\!+\!bcy = \smash{({\overbrace{\color{#0a0}{ax\!+\!by}}^{\textstyle\color{#c00}{\bf 1}}}\!)} c\, =\, c\\[.3em] \color{#90f}{(a,\ \ \ b)}=&\,\color{#c00}{\bf 1},\,\ a\ \mid\ bc\ \ \Rightarrow\ a\ \mid\ c.\ \ \ {\bf Pf}\!:\ a\ \mid\,\ ac,\ bc\, \Rightarrow\, a\,\mid (ac,\ \ bc)\, =\, \color{#90f}{(a,\ \ \ b)}\ \, c\, =\, c\\[.3em] \rm A +{B}\ =&\rm \,\color{#c00}{\bf 1},\, A\supseteq\! {BC}\, \Rightarrow A \supseteq {C}.\,\ {\bf Pf}\!:\:\! A \supseteq\! A{C},\!{ BC}\!\Rightarrow\! A\supseteq A{C}\!+\!\!{BC} =(A+{B}){C} = C \end{align}}

Note the (common) first proof boils down to scaling by $$\,c\,$$ the $$\rm\color{#0a0}{Bezout\ equation}$$ for $$\,\gcd(a,b) = 1.\,$$ In the second proof we can read $$\,\color{#90f}{(a,b)}\,$$ either as a gcd or an ideal. Read as a gcd the proof employs the universal property of the gcd $$\, d\mid m,n\iff d\mid (m,n)\,$$ and the gcd distributive law $$\,(ac,bc) = (a,b)c.\,$$ In the first proof (by $$\rm\color{#0a0}{Bezout}$$) this gcd arithmetic is traded off for integer arithmetic, so the gcd distributive law becomes the distributive law in the ring of integers. The third proof generalizes the second proof from coprime integers to coprime (i.e. comaximal) ideals $$\rm A,\, B,\,$$ i.e. $$\rm\, A+B= 1.\,$$ The second proof is the special case of the third when the ideals are principal $$\, {\rm A}\! =\! (a),\ {\rm B}\! =\! (b),\ {\rm C} \!=\! (c).\,$$ Recall "contains = divides" for principal ideals $$\,(a)\supseteq (b)\!\iff\! a\mid b.$$

• so how would you go about proving it then? Commented Dec 7, 2012 at 1:53
• Since $A$ is a UFD, we can let $a=p_1p_2...p_n$ for some primes $p_1,p_2,...,p_n \in A$. Then, for all $i$, $p_i$ does not divide b. But I don't know how to proceed. Commented Dec 7, 2012 at 1:55
• So you don't need a prime factorization argument? Commented Dec 7, 2012 at 1:57
• No, factorization into primes isn't needed, one needs only the existence of gcds, as the second proof above shows. The gcd argument is more general since there are domains which have no primes yet gcds exist, e.g. the ring of all algebraic integers, which has no irreducibles (so no primes) since every element factors, e.g. $\rm\: a = \sqrt{a}\cdot \sqrt{a}\ \$ Commented Dec 7, 2012 at 2:32

HINT:

For $$a$$, $$b$$, $$c$$ elements of a (GCD) ring we have

$$(a, b c) = (a, (a,b) c)$$

both sides being equal to $$(a, a c , b c)$$. Therefore, if $$(a,b)=1$$ then $$(a, b c) = (a,c)$$

$$\bf{Added:}$$ Similarly

$$(a,b)(a,c) = (a^2, a b, a c, b c)= (a^2, a(b,c), b c)$$

Therefore, if $$(b,c)=1$$ then RHS becomes $$(a^2, a, b c) = (a, b c)$$ and so $$(a,b)(a,c) = (a, b c)$$

• There already occur here in many places, e.g. here in $2010.\ \$ Commented Jul 13, 2022 at 18:03
• @Bill Dubuque: I have no claim to originality, simply playing with the gcd equalities. Btw, I like your solutions a lot, and am sold on Prufer rings :-) Commented Jul 13, 2022 at 18:24
• Great. My comment was meant mainly to help readers locate further discussion on such. Commented Jul 13, 2022 at 18:27