UFD is GCD Domain

Theorem

Let $A$ be a unique factorisation domain.

Then $A$ is a GCD domain.

Proof

Let $x \backslash y$ denote $x$ divides $y$.

Let $x,y \in A$, with factorizations:

$x = u x_1 \cdots x_r,\quad y = v y_1 \cdots y_s$

with $u,v$ units and the $x_i$, $y_i$ irreducible.

We arrange the factorizations as follows:

$x = u \left({x_1 \cdots x_t}\right) x_{t + 1} \cdots x_r$

$y = v \left({y_1 \cdots y_t}\right) y_{t + 1} \cdots y_s$

where:

• $t \le \operatorname{min} \left\{{r, s}\right\}$
• For $i = 1, \ldots, t$, $x_i$ and $y_i$ are associates
• For any $i \in \left\{{t+1, \ldots, r}\right\}$, $j \in \left\{{t+1, \ldots, s}\right\}$, $x_i$ and $y_j$ are not associates.

Let $d = x_1 \cdots x_t$ (recall that the empty product is $1$, i.e. $d = 1$ when $t = 0$).

We claim that $d$ is a greatest common divisor for $x$ and $y$.

Certainly $d \backslash x$ and $d \backslash y$, so let $f$ be another common divisor of $x$ and $y$.

We can find $w, z \in A$ such that $x = u f w$, and $y = v f z$.

If $f$ is unit, then trivially $f \backslash d$.

Suppose $f \nmid d$.

Then the factorization of $f$ must contain an irreducible that does not divide $d$.

But then some element $x_j$, $j > t$ must divide some $y_k$ where $k > t$.

This is a contradiction.

Therefore $f \backslash d$.

$\blacksquare$