Greatest Common Divisors in UFDs

Motivating Remark.
In the ring of integers $\mathbb{Z}$, we can unambiguously choose the greatest common divisor of $a$ and $b$ to be a positive integer. However, in a general unique factorization domain, there is no canonical way to select a “positive” representative. Therefore, when we define a gcd in a UFD, it is only well-defined up to associates.

Definition (p-valuation).
Let $D$ be a UFD and let $p$ be a prime element in $D$. For $a \in D \setminus \{0\}$, we define the $p$-valuation of $a$, denoted $v_p(a)$, as the largest non-negative integer $n$ such that $p^n \mid a$.

We also define $v_p(0) := \infty$.

Lemma (Basic Properties of p-Valuation).
Let $D$ be a UFD and let $\mathcal{P}$ be a choice of representatives for the set of prime elements in $D$ up to associates (i.e., one prime per associate class. In $\mathbb{Z}$, we pick the positive primes). Then:

  1. If $p \sim q$, then $v_p(a) = v_q(a)$ for all $a \in D$. So $v_{[p]}(a)$ is well-defined on associate classes.

  2. Every nonzero $a \in D$ has a unique factorization:

    \[a = u \prod_{p \in \mathcal{P}} p^{v_p(a)}, \quad \text{where } u \in D^\times\]
  3. If $a \sim b$, then $v_p(a) = v_p(b)$ for all $p$.
  4. $a \mid b$ if and only if $v_p(a) \leq v_p(b)$ for all $p \in \mathcal{P}$.
  5. $v_p(ab) = v_p(a) + v_p(b)$.
  6. $v_p(a + b) \geq \min { v_p(a), v_p(b) }$. If $v_p(a) \ne v_p(b)$, then equality holds.

Definition (Greatest Common Divisor).
Let $D$ be a UFD and let $a_1, \ldots, a_m \in D \setminus \{0\}$. Define the greatest common divisor of $a_1, \ldots, a_m$ to be the associate class:

\[\gcd(a_1, \ldots, a_m) := \left[ \prod_{p \in \mathcal{P}} p^{\min_i v_p(a_i)} \right]\]

This is well-defined up to associates. Any representative $d$ of this class satisfies:

  1. If $\gcd(a_1,\ldots, a_m) = [d]$, then $d \mid a_i$ for all $i$, and

    \[\gcd\left(\frac{a_1}{d}, \ldots, \frac{a_m}{d} \right) = [1]\]

  2. For any element $c \in D\setminus\{0\}$,

    \[\gcd(ca_1, \ldots, ca_m) = [c] \cdot \gcd(a_1, \ldots, a_m)\]

Theorem (Bézout’s Identity).
Let $D$ be a principal ideal domain (PID), and let $a, b \in D$. Suppose $\gcd(a, b) = d$, where $d$ is a fixed representative of the gcd up to associates. Then:

\[\langle a, b \rangle = \langle d \rangle,\]

and there exist $x, y \in D$ such that

\[ax + by = d.\]

Proof.
Since $D$ is a PID, the ideal generated by $a$ and $b$ is principal. That is, there exists $d’ \in D$ such that

\[\langle a, b \rangle = \langle d' \rangle.\]

Then $d’ \mid a$ and $d’ \mid b$, so $d’$ is a common divisor of $a$ and $b$. Let $\mathcal{P}$ be a choice of representatives of the prime elements of $D$ up to associates. Since

\[v_p(d') \le \min \{ v_p(a), v_p(b) \} = v_p(d),\]

it follows that $d’ \mid d$.

On the other hand, since $d = \gcd(a, b)$, we know $d \mid a$ and $d \mid b$, so $a, b \in \langle d \rangle$, and hence

\[\langle d'\rangle = \langle a, b \rangle \subseteq \langle d \rangle.\]

This implies that $d’ \mid d$. Since we also have $d \mid d’$, we know that $d \sim d’$, i.e., they are associates.

Therefore,

\[\langle a, b \rangle = \langle d'\rangle = \langle d \rangle.\]