GCD expressed with irreducible elements in a unique factorization domain Let $R$ be a unique factorization domain (UFD). Given $a,b \in R$ not simultaneously equal to zero, an element $d \in R$ is by definition a greatest common divisor (GCD) of $a$ and $b$ provided:


*

*$d \mid a$ and $d \mid b$.

*For all $d' \in R$ such that $d' \mid a$ and $d' \mid b$, we have that $d' \mid d$.


Let $U(R) := \{\,\text{units in $R$}\,\}$ and assume $a,b \neq 0$, $a,b \notin U(R)$. Since $R$ is a UFD, there exist $u,v \in U(R)$, irreducible elements $p_1,\dots,p_s \in R$ which are mutually non associate, $d_1,\dots,d_s,e_1,\dots,e_s \in \mathbb{N}$ such that:
\begin{equation}
 a = u \cdot p_1^{d_1} \cdots p_s^{d_s} \, , \quad b = v \cdot p_1^{e_1} \cdots p_s^{e_s}
\end{equation}
For all $1 \leq i \leq s$, let $f_i := \min\{d_i,e_i\}$. We want to prove that a GCD of $a$ and $b$ is:
\begin{equation}
 c := p_1^{f_1} \cdots p_s^{f_s}
\end{equation}
 A: We need to verify conditions 1 and 2 of the previous definition. When it comes to condition 1, we have no difficulties. In fact, we have that $c \mid a$ since:
\begin{equation}
 a = u \cdot p_1^{d_1} \cdots p_s^{d_s} = (p_1^{f_1} \cdots p_s^{f_s}) \cdot (u \cdot p_1^{d_1-f_1} \cdots p_s^{d_s-f_s}) = c \cdot (u \cdot p_1^{d_1-f_1} \cdots p_s^{d_s-f_s})
\end{equation}
Similarly, we have that $c \mid b$, thus condition 1 is satisfied.
Now, given an element $d \in R$ such that $d \mid a$ and $d \mid b$, such element is nonzero by definition of divisibility. If $d \in U(R)$, then $d \mid c$ because $c = d \cdot (d^{-1} \cdot c)$. Assume $d \notin U(R)$. Then, by definition of UFD, there exist $w \in U(R)$, irreducible elements $q_1,\dots,q_r \in R$ which are mutually not associate, $g_1,\dots,g_r \in \mathbb{N}^*$ such that:
\begin{equation}
 d = w \cdot q_1^{g_1} \cdots q_r^{g_r}
\end{equation}
We're now going to use this fact:

$d \mid a$ implies that every irreducible factor of $d$ is associated to an irreducible factor of $a$.

By relabeling (which is legitimate since $R$ is a commutative ring), we can assume that $q_i$ is associated to $p_i$ for all $1 \leq i \leq r$. In particular, since $p_1,\dots,p_r$ are mutually not associate, for all $1 \leq i \leq n$ we have that $q_i$ is only associated to $p_i$, thus $g_i \leq d_i$. Similarly, since $d \mid b$ we have that $g_i \leq e_i$ for all $1 \leq i \leq s$. Thus by definition of $f_1,\dots,f_s$ we also have that $g_i \leq f_i$ for all $1 \leq i \leq s$. Now, by definition of associate elements, we have that $q_i \mid p_i$ for all $1 \leq i \leq r$, hence $p_i = q_i \cdot x_i$ for some $x_i \in R$. Thus:
\begin{align*}
 c & = (p_1^{f_1} \cdots p_r^{f_r}) \cdot (p_{r+1}^{f_{r+1}} \cdots p_s^{f_s}) \\ & = \bigl((q_1^{f_1} \cdot x_1^{f_1}) \cdots (q_r^{f_r} \cdot x_r^{f_r})\bigr) \cdot (p_{r+1}^{f_{r+1}} \cdots p_s^{f_s}) \\ & = d \cdot (q_1^{f_1-g_1} \cdots q_r^{f_r-g_r}) \cdot (x_1^{f_1} \cdots x_r^{f_r}) \cdot (p_{r+1}^{f_{r+1}} \cdots p_s^{f_s}) \cdot w^{-1}
\end{align*}
This proves that $d \mid c$ and so condition 2 is verified. Hence c is a GCD of $a$ and $b$ and we're done.
A: The result follows from the properties of the ''less than'' relation and minimum formation.


*

*We have $f_i= \min\{e_i,d_i\}\leq e_i,d_i$ for all $i$.

*If $f'_i \leq e_i$ and $f'_i\leq d_i$, then $f'_i\leq \min\{e_i,d_i\}=f_i$ for all $i$.
