Proof of general Euclid's Lemma in a UFD (by Euclidean algorithm?)

Solution 1:

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

Below are $\:\!2\:\!$ proofs, using $(1)$ gcds, and $(2)$ existence and uniqueness of prime factorizations.

$(1)\ $ By gcds: $\rm\ a\mid ac,bc\Rightarrow a\mid \color{0A0}{(ac,bc)\!\:\smash{\overset{\rm\color{#c00}{DL}}=(\overbrace{a,b}^{\large \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 are 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 $ $ 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 = ({\overbrace{\color{#0a0}{ax\!+\!by}}^{\large\color{#c00}{\large \bf 1}}}\!) c\, =\, c\\[.1em] \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)\, =\, (a,\ \ \ b)\ \, c\, =\, c\\[.1em] \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 that "contains = divides" for principal ideals, i.e. $\,(a)\supseteq (b)\iff a\mid b.$