# 代數導論二 Week 3 (Part 2) - Greatest Common Divisors

[TOC]

## 定義：倍數、整除

:::warning

假定 $R$ 是一個交換環，$x, y \in R$，且 $x \neq 0$。若：

$$
\exists a \in R.y = ax
$$

則稱 $y$ 是 $x$ 的倍數 (*multiple*)，或說 $x$ 整除 $y$。並且寫作：

$$
x \mid y
$$

:::

## 定義：最大公因數

:::warning

假定 $R$ 是一個交換環，且 $x, y \in R$，並且 $x \neq 0$。若 $d \in R$ 滿足下列兩點

1. $d$ 可以同時整除 $x, y$：

$$
\begin{align}
& d \mid x
\newline
&d \mid y
\end{align}
$$

2. 任何同時整除 $x, y$ 的元素，都必定可以整除 $d$

$$
\begin{cases}
d' \mid x
\newline
d' \mid y
\end{cases}
\Rightarrow d' \mid d
$$

則稱 $d$ 是一個 $x, y$ 的最大公因數。並且用以下符號表示：

$$
d = \gcd (x, y)
$$

:::

$d \mid x$ 已經隱含 $0 \neq d$ 了，所以這個 $\gcd$ 一定不會是 $0$。

### 觀察：兩個元素生成的 Principal Ideal 也可以被最大公因數生成

:::danger

假定 $R$ 是一個交換環，且 $a, b \in R$，其中 $a \neq 0$ 且 $b \neq 0$。並令 $d$ 為一個 $a, b$ 的最大公因數：

$$
d = \gcd(a, b)
$$

**若 $(a, b)$ 是一個 *principal ideal***，則 $a, b$ 生成的 *ideal* 恰好就是 $\gcd(a, b)$ 生成的 *ideal*：

$$
\begin{align}
&(a, b) \text{ principal}
\newline
& \Rightarrow (d) = (a, b)
\end{align}
$$

:::

Since $(a, b)$ is principal, there's a $0 \neq \alpha \in R$, such that:

$$
(a, b) = (\alpha)
$$

then

$$
\begin{align}
&a \in (\alpha) \text{ and }b \in (\alpha)
\newline
&\Rightarrow a = \alpha x \text{ and }b = \alpha y
\newline
&\Rightarrow \alpha \mid a \text{ and }\alpha \mid b
\newline
&\Rightarrow \alpha \mid d
\newline
&\Rightarrow (d) \subseteq (\alpha) = (a, b)
\end{align}
$$

Since $d$ is gcd, then

$$
\begin{align}
&d \mid a \text{ and }d \mid b
\newline
&\Rightarrow a \in (d) \text{ and }b \in (d)
\newline
&\Rightarrow (a, b) \subseteq (d)
\end{align}
$$

所以就證明完了：

$$
\begin{align}
(d) \subseteq (a, b) = (\alpha) \subseteq (d)
\Rightarrow (d) = (\alpha)
\end{align}
$$

> 一定要是 *principal* 的時候兩個才會相等。比如說 $\Bbb Z[x]$ 跟 $(p, x)$。這時候 $\gcd(p, x) = 1$，但是 $(p, x) \neq (1)$。