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}
Best Answer
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:
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.
Edit: we are now going to prove the fact we used. More precisely, we are going to prove the following result.
Let $R$ be a unique factorization domain, let $a,b \in R$, $a,b \neq 0$, $a,b \notin U(R)$ and let $a = c_1 \cdots c_n$, $b = d_1 \cdots d_m$ factorizations of $a$ and $b$ in irreducible elements. If $b \mid a$, then $m \leq n$ and there exists a permutation $\sigma : \{1,\dots,n\} \to \{1,\dots,n\}$ such that $d_i$ is associated to $c_{\sigma(i)}$ for all $1 \leq i \leq m$.
Indeed, if $b \mid a$, then there exists $x \in R$ such that $a = b \cdot x$.
Assume $x \in U(R)$. In this case, by defining $d_m' : = d_m \cdot x$, we have two factorizations of $a$ in irreducible elements, that is $a = c_1 \cdots c_n$ and $a = d_1 \cdots d_{m-1} d_m'$. Since $R$ is a unique factorization domain, we must have $n = m$ and a permutation $\sigma : \{1,\dots,n\} \to \{1,\dots,n\}$ such that $d_i$ is associated to $c_{\sigma(i)}$ for all $1 \leq i \leq m - 1$ and $d_m'$ is associated to $c_{\sigma(m)}$. In addition, since we are assuming $x \in U(R)$, the element $d_m'$ is also associated to $d_m$ and therefore $d_m$ is associated to $c_{\sigma(m)}$ by simmetry and transitivity of the association relation.
Now assume $x \notin U(R)$. Since $a \neq 0$ by hypothesis, we have $x \neq 0$. Since $R$ is a unique factorization domain, there exists a factorization in irreducible elements $x = e_1 \cdots e_s$. But then we have two factorizations of $a$ in irreducible elements, that is $a = c_1 \cdots c_n$ and $a = d_1 \cdots d_m \cdot e_1 \cdots e_s$. Once again, by using the hypothesis that $R$ is a unique factorization domain, we get $n = m + s$ and a permutation $\sigma : \{1,\dots,n\} \to \{1,\dots,n\}$ such that $d_i$ is associated to $c_{\sigma(i)}$ for all $1 \leq i \leq m$ and $e_i$ is associated to $c_{\sigma(m + i)}$ for all $1 \leq i \leq s$. In particular, we have what we wanted to prove.