# 代數導論二 Week 3 (Part 3) - Euclidean Algorithm

[TOC]

## 定理：輾轉相除法

:::danger

假定 $R$ 是一個 *Euclidean Domain*，$a, b \in R$，且 $b \neq 0$。假定 $r_n$ 是對 $a, b$ 使用輾轉相除法之後時，出現的最後一個非零餘數。則：

1. $r_n$ 就是 $a, b$ 的最大公因數：

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

2. $r_n$ 可以生成 $(a, b)$：

$$
(r_n) = (a, b)
$$

:::

這邊的 $r_n$ 是指：如果一直作輾轉相除法：

$$
\begin{align}
\overbrace{\boxed{r_0}}^{a} &= \overbrace{\boxed{r_1}}^{b}q + r_2
\newline
r_1 &= r_2q_2 + r_3
\newline
r_2 &= r_3q_2 + r_4
\newline
\vdots
\newline
r_{n-3} &= r_{n-2}q_{n-2} + r_{n-1}
\newline
r_{n-2} &= r_{n-1}q_{n-1} + r_n
\newline
\boxed{r_{n-1}}&= r_nq
\end{align}
$$

最後一定會做到一個餘數是 $0$ 的步驟 (因為 $0 \leq N(r_i) < N(r_{i - 1})$，而且每個 $N(r_i)$ 都是正整數)。最後剩下的那個 $r_n$ 就是上面所說的。

*Euclidean Domain* 中，每個 *ideal* 都是 *principal ideal*，而前面已經證明過「交換環中若兩個元素生成的 *ideal* 是個 *principal ideal*，那麼這個 *ideal* 就可以用兩者的最大公因數生成」。所以如果已經有 $(1)$，那就自動有 $(2)$。因此只要證明第一點就可以了：

1. 首先證明 $r_n$ 是一個 $a, b$ 的公因數，方法是從後面往前面遞推，一路得到 $r_n$ 可以同時整除 $a$ 跟 $b$：

1. 首先，顯然有：

$$
r_n \mid r_n \quad (1)
$$

2. 接下來，因為 $r_{n-1} = r_nq$，所以也有：

$$
r_n \mid r_{n-1} \quad (2)
$$

所以就可以發現：

$$
r_{n-2} = \underbrace{r_{n - 1}}_{r_{n} \mid r_{n-1}}q_{n-1} + \underbrace{r_{n}}_{r_n \mid r_n}
$$

因此：

$$
r_n \mid r_{n-2}
$$

3. 如法炮製，發現 $r_n$ 可以整除 $r_{n-3}$：

$$
r_{n-3} = \underbrace{r_{n-2}}_{r_n \mid r_{n-2}}q_{n-2} + \underbrace{r_{n-1}}_{r_n \mid r_{n-1}}
$$

4. 因為 $r_{n}$ 可以整除 $r_{n - 2}$ 跟 $r_{n - 3}$，所以可以整除 $r_{n - 4}$。因此一般地來說，就有 $r_n \mid r_{k}$ 且 $r_n \mid r_{k-1}$，所以 $r_n \mid r_{k-2}$：

$$
r_n \mid \underbrace{r_{k}q_{k} + r_{k-1}}_{r_{k-2}}
$$

5. 所以做到最後一步時，就會有：

$$
\begin{align}
r_n \mid \underbrace{r_1}_{b}
\newline
r_n \mid \underbrace{r_0}_{a}
\end{align}
$$

也就是：

$$
\boxed{r_n \mid a \text{ and }r_n \mid b}
$$

2. 接下來要證明「最大」，方法就是從前面帶回去：

1. 因為 $d \mid r_0$ 且 $d \mid r_1$，所以 $d \mid r_2$：

$$
\underbrace{r_0}_{d \mid r_0} = \underbrace{r_1}_{d \mid r_1}q_1 + r_2
$$

2. 因此一般地來說：

$$
\begin{align}
&(d \mid r_{k-2}) \text{ and }(d \mid r_{k-1})
\newline
&\Rightarrow \overbrace{r_{k-2}}^{(d \mid r_{k-2})} = \overbrace{r_{k-1}}^{(d \mid r_{k-1})}q_{k-1} + r_k
\newline
&\Rightarrow d \mid r_{k}
\end{align}
$$

3. 所以一直遞推，就會得到：

$$
\boxed{d \mid r_n}
$$

4. 接下來就可以證明最大。假定 $d'$ 是一個 $a, b$ 的公因數，因為 $d'$ 是最大公因數，所以由最大公因數的定義知道：所有 $a, b$ 的公因數都要能夠整除他：

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

5. 另外一方面，因為 $d \mid r_n$，所以任何能整除 $d$ 的東西都要能整除 $r_n$。所以就發現 $d'$ 也必須能夠整除 $r_n$：

$$
d' \mid d \text{ and } d \mid r_n \Rightarrow d' \mid r_n
$$

這樣就證明完「最大」的部分了。

> **使用 PID 性質的版本**：就是從前面的步驟，然後用 *PID* 中「能夠生成 2 元素所生成的 Ideal」等價於「最大公因數」證明。
>
> 由 $(r_n \mid d)$ 且 $(d \mid r_n)$。這就表示：
>
> $$
> (d) \subseteq (r_n) \text{ and }(r_n) \subseteq (d)
> $$
>
> 換句話說：
>
> $$
> (d) = (r_n)
> $$
>
> 也就是 $r_n$ 跟 $d$ 生成的 *ideal* 都是一樣的。又因為 $d$ 生成的 *ideal* 就是 $(a, b)$，所以實際上 $r_n$ 生成的 *ideal* 恰好就是 $(a, b)$：
>
> $$
> \underbrace{(d)}_{(a, b)} = (r_n)
> $$
>
> 如果 $(a, b)$ 是 *principal ideal*，那麼能生成 $(a, b)$ 的元素都是 $a, b$ 的一個最大公因數。所以就證明了 $r_n$ 是 $a, b$ 的一個最大公因數。
>

## 推論：Bezout's Identity

:::danger

假定 $R$ 是一個 *Euclidean Domain*，且 $a, b, N \in R$。則以下兩個敘述等價：

1. 以下的方程式的 $x_0, y_0$ 在 $R$ 中有解：

$$
a x_0 + by_0 = N \quad a, b, N \in R
$$

2. $N$ 是 $\gcd(a, b)$ 的倍數：

$$
\gcd(a, b) \mid N
$$

:::

上面到下面是顯然，下面到上面是因為：上面那條方程有解的意思是「$N$ 在 $(a, b)$」裡面，但是 $(a, b) = (\gcd(a, b))$。