UFD is GCD Domain

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ be a unique factorisation domain.

Then $A$ is a GCD domain.


Proof 1

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

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

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

where:

$u, v$ are units
the $x_i$, $y_i$ irreducible.


We arrange the complete factorizations as follows:

$x = u \paren {x_1 \cdots x_t} x_{t + 1} \cdots x_r$
$y = v \paren {y_1 \cdots y_t} y_{t + 1} \cdots y_s$

where:

$t \le \min \set {r, s}$
For $i = 1, \ldots, t$, $x_i$ and $y_i$ are associates
For any $i \in \set {t + 1, \ldots, r}$, $j \in \set {t + 1, \ldots, s}$, $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 \divides x$ and $d \divides y$.

So, let $f$ be another common divisor of $x$ and $y$.

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

If $f$ is a unit, then $f \divides d$ by definition.


Aiming for a contradiction, suppose $f \nmid d$.

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

Call this irreducible element $g$.

We have that:

$g$ must divide some $x_j$ where $j > t$

and

$g$ must divide some $y_k$ where $k > t$.

Either:

$g$ is a unit, contradicting its irreducibility

or:

$x_j$ and $y_k$ are not irreducible, which is a contradiction also.

Hence by Proof by Contradiction:

$f \divides d$

and so $x$ and $y$ have a greatest common divisor.

$\blacksquare$


Proof 2

UFD is GCD Domain/Proof 2