# 代數導論 Week 4 (Part 2) - Greatest Common Divisor in UFD

[TOC]

## 觀察：UFD 可以從分解找最大公因數

:::danger

Suppose that $R$ is an UFD, $a, b \in R \setminus \{0\}$ are not unit. Suppose that

$$
a = u \prod_{i = 1}^{n}p_i^{e_i}
$$

$$
b = v \prod_{i = 1}^{n}p_i^{f_i}
$$

where $p_i$ are distinct irreducible and $e_i, f_i \in \Bbb Z^{+} \cup \{0\}$. Then

$$
d = \prod_{i = 1}^{n}p_i^{\min(e_i, f_i)}
$$

is a greatest common divisor of $a$ and $b$.

:::

Suppose that

$$
d' \in R \setminus \{0\}
$$

and

$$
d' \mid a \text{ and }d' \mid b
$$

==GOAL: $d\mid d'$==

$d'$ can be factorized into powers of irreducibles $p_1 \dots p_n$. i.e.

$$
d' = u\prod_{i = 1}^{n}p_i^{g_i}
$$

where $g_{i} \in \Bbb Z^+ \cup \{0\}$ and $u$ is a unit

> $d'$ 中的 *irreducible* 只能出現 $p_1 \dots p_n$，不然就會發現 $a$ 跟 $b$ 可以找到另外一個分解，跟分解的唯一性矛盾

Since

$$
d' \mid a \Rightarrow g_u \leq e_i
$$

Similarily

$$
d' \mid b \Rightarrow g_i \leq f_i
$$

Combining these two results we have

$$
g_i \leq \min(e_i, f_i)
$$

So

$$
d = d' \left(\prod_{i = 1}^{n}p_i^{\min(e_if_i) - g_i}\right) \Rightarrow d' \mid d
$$