UFD implies GCD

Question

Let $R$ be an integral domain. Assume $R$ is UFD, show $R$ is GCD.

I did not find proof anywhere except one in proofwiki, but unfortunately there is a crucial part which I do not understand. https://proofwiki.org/wiki/UFD_is_GCD_Domain

Proof: Let $x,y\in R\setminus \{0\}$. As $R$ is UFD, we can write $x=ux_1x_2...x_r$, $y=vy_1y_2...y_s$, $u,v,x_i,y_j\in R$.

If $\exists x_i\in\{x_1,...,x_r\},y_j\in\{y_1,...,y_s\}$ such that $x_i$ and $y_j$ are associate., then rearrange $\{x_1,...,x_r\}$,$\{y_1,...,y_s\}$ such that $x=u(x_1...x_t)x_{t+1}...x_r, y=v(y_1...y_t)y_{t+1}...y_{s}$ where $1\leq t\leq min(r,s)$ and $x_i,y_i$ are associate for all $i\leq t$ and $\not\exists i \in[t+1,r],j\in[t+1,s]$ such that $x_i,y_j$ are associate.

Let $d:=x_1...,x_t$ if such $t$ exists otherwise let $d:=1$.

Claim: $d$ is a greatest common divisor of $x$ and $y$. Certainly, $d|x$ and $d|y$. Let $f\in R\setminus \{0\}$ such that $f|x$ and $f|y$(i.e. $\exists w,z\in R\setminus\{0\}$ such that $x=fw,y=fz$). We need to show $f|d$.

We assume $f$ is not a unit otherwise $f|d$ and we are done. Hence assume $f$ is not a unit and assume for contradiction that $f$ does not divide d.

Then the author claims $f$ must contain in its prime factorisation a irreducible element which does not divide $d$.

Why should this be true? For example $\mathbb{Z}$ is a UFD and 4 does not divide 6 but all irreducible factors of 4, namely 2,-2, divide 6.

Answer 1

Then the author claims $f$ must contain in its prime factorisation a irreducible element which does not divide $d$.
Why should this be true? For example $\mathbb{Z}$ is a UFD and 4 does not divide 6 but all irreducible factors of 4, namely 2,-2, divide 6.

It's true that "$f$ does not divide $d$ implies there is an irreducible dividing $f$ that doesn't divide $d$" is a false statement.

However, your example does not take into account the full context, that $f$ divides $x,y$. If $4$ divides both $x$ and $y$, then both $2$'s in the factorization would have been grouped into $d$, and so $6$ would not be a valid option for $d$.

If all irreducible factors of $f$ appeared (separately, as associates) as a irreducible factors of $d$, then by the way $d$ was constructed, the factorization of $f$ (with multiplicities and all) would be listed in $d$'s factorization, and $f|d$, which we have assumed is not the case. Therefore there must be an irreducible factor of $f$ not associate to any irreducible in $d$'s factorization.

Answer 2

The PW argument is either incomplete or incorrect, and it is impossible to decide which from what is written. Likely the author assumes the reader can complete it because they assume that it is "obvious" by construction that $\:\!d\:\!$ correctly accounts for multiplicity, i.e. $\,p^k\:\!|\:\! d\!\iff\! p^k\:\!|\:\! x,y,\,$ for prime $\,p\,$ (so your counterexample with a higher multiplicity divisor does not apply here).

---

It is simpler and clearer to present the proof as follows. Let $\,d\mid x,y\,$ be a common divisor of $\,x,y\,$ having $\rm\color{#90ff}{max\ \#prime}$ factors (counting multiplicity), so $\,x=ad,\, y = bd\,$ and $\,a,b\,$ are $\rm\color{#c00}{coprime}$ (else $\,p\mid a,b\,$ yields a $\rm\color{#90f}{bigger}$ common factor $\,pd)$. That $\,d\,$ is a (divisibly) greatest common divisor (i.e. $\,c\:\!|\:\!x,y\Rightarrow c\:\!|\:\! d)\,$ follows by the simple induction below, using UFD $\Rightarrow$ $\rm\color{#0a0}{EL}$ (Euclid's Lemma)

Lemma $\ \color{#c00}{a,b\,\ \rm{coprime}},\,$ $\,c\mid \smash[t]{\overbrace{ad,bd}^{\large x,\,\ y}}\phantom{|^{|^{|}}}\!\!\!\Rightarrow\, c\mid d,\,$ in a UFD $ $ (or $\,c\! =\!\,$ product of primes in any domain)

Proof $ $ Induct on $\,n =$ #primes (with multiplicity) in a prime factorization of $\,c.\,$ Base case $\,n\!=\!0\,$ is clear since then $\,c\,$ is a unit. Else $\,n\ge 1\,$ so some prime $\,p\mid c\mid ad,bd\,$ but $\,\color{#c00}{\rm not}\ (p\mid \color{#c00}a\ \,\&\,\ p\mid\color{#c00} b),\,$ so wlog $\,p\nmid b,\,$ so $\,p\mid bd\underset{\rm\color{#0a0}{EL}}\Rightarrow p\mid d,\,$ so $\,c/p\mid a(d/p),b(d/p),\,$ so by induction $\,c/p\mid d/p,\,$ so $\,c\mid d$.

---

Remark $ $ The above proof avoids the need to explicitly account for multiplicity by using EL (and cancellation) to (inductively) match up each prime factor of $\,c\,$ with an associate prime factor of $\,d\,$ (but it avoids any cumbersome need to explicitly deal with associateness). The proof is essentially an (inductive) proof of the gcd distributive law $\,(ad,bd)= (a,b)d,\,$ in the special case $\,(a,b)\!=\!1$.

You may find it instructive to compare the above proof with a similar inductive proof of Euclid's Lemma - proof $(0)$ here. Alternative to the above inductive proof, we can account for multiplicity by using multisets of primes (as in proof $(2)$ there) or, equivalently, by applying rudimentary properties of $p$-adic valuations: $\nu_p(n) = k\iff p^k\,||\, n\iff n = p^k a,\ p\nmid a$.

Answer 3

As the previous answers have addresses your problem(and the proof you posted is, admittedly, confusing), I just wish to provide a clean and easy-to-read proof to my taste. Our goal is to show U.F.D. implies the existence of gcd for any two elements $\{a,b\}$, or better, any nonempty set $B \subset R-0$. In general the messy situation would be greatly improved with the help of the length function. i.e. $l(a)=n$ if $a = u p_1 p_2 ... p_n$. (let $l(u)=0$ for units and $l(0)=-\infty$). Since in U.F.D all elements admit such unique expansion up to associates, the function is well-defined with $l(ab) = l(a)+l(b)$.

Assume $D = \{x \in R: x \ne 0; x|b, \forall b \in B \}$. It can be checked that $x|b$ implies $l(x)\le l(b)$. Hence $D$ is a set of integers which is bounded by $l(b)$ (any fixed $b$ would serve as our upper bound here). Simply choose the maximum element (not necessarily unique) and call it $a$ = gcd$(B)$.

The tricky part of the proof lies in: if $a' \in D$, then $a' |a$. Since by unique factorization one can factorize $a$ and $a'$, we note that, up to asscociates, they will have common factor $c = p_{i_1} ... p_{i_k}$ of maximal length $l(c)$. Write $a = cy$ and $a' = cy'$.

If $y'$ is a unit, then we are done because we can find $a'u' =cy'u'=c1=c$, i.e. $a'u'y = a$. Otherwise $y'$ at least contains one irreducible $p$. (Possibly $y' = p$ in the case that $y'$ is irreducible, or $y'$ can be decomposed into irreducibles) and $l(cp) = l(c) + l(p) = l(c)+1$.

If $cp|a$, then $c$ is not the maximal common factor, hence $cp \nmid a.$ So $p \nmid y$. Let $b \in B$ be arbitrary, and write $b = az = cyz$. As $a '|b, cp|b$, so $cp|cyz$, which implies that $p|yz$. As $p$ is prime (here one shall use the essential fact that in U.F.D irreducible elements are prime) and as $p \nmid y$, $p|z$. So $ap|b$. As $b \in B$ is arbitrary, it follows that $ap \in D$ is a divisor with $l(a) < l(ap)$, contradicting the choice of $a$.

*In general it would be easier to show the gcd of two elements exists by explicitly writing out $a = u{p_1}^{e_1}... {p_n}^{e_n}$ and $b=v{p_1}^{f_1}...{p_n}^{f_n}$ and $d= {p_1}^{min(e_1,f_1)}...{p_n}^{min(e_n,f_n)}$.