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

[TOC]

> 接下來的東西基本上都是數論相關的。

這邊也是一樣，定在有 $1$ 的交換環。這些東西某種程度上都是要來模擬整數，就是把一些整數上面有的性質抽出來，接下來問如果環上有這些性質，會不會有類似整數的結論？

## 定義：Norm on Integral Domain

:::warning

Suppose $R$ is a commutative ring with $1$. Any function

$$
N: R \to \Bbb Z^+ \cup\{0\}
$$

with

$$
N(0) = 0
$$

is called a norm on the integral domain $R$. If furthermore

$$
N(a) > 0 \quad \forall a \neq 0
$$

then $N$ is called a positive norm

:::

*Euclidean Domain* 就是一個 *integral domain* 上面加一個 *norm*，也就是一個把環打到正整數或 $0$ 的函數，唯一的要求就是把 $0$ 打到 $0$。

### 例子：整數

舉例來說 $\Bbb Z$ 搭配取絕對值函數當 *norm*，會是一個 *Euclidean Domain*

$$
\begin{align}
\Bbb Z &\to \Bbb Z^{+} \cup \{0\}
\newline
n &\mapsto |n|
\end{align}
$$

### 例子：高斯整數

又比如說：收集複數平面上的格子點 $\Bbb Z[i]$。也就是：

$$
\{a + bi \mid a, b \in \Bbb Z\}
$$

並且定義 *norm* 為：

$$
\begin{align}
a + bi \mapsto a^2 + b^2
\end{align}
$$

其中，$a, b \in \Bbb Z$。則這個函數也是一個 *norm*。

## 定義：Euclidean Domain

> 白話文就是上面有除法原理的 *integral domain*：

:::warning

Suppose $R$ is a integral domain. $R$ is called a Euclidean Domain if there's some norm $N$ such that forall $a, b \in R$ with $b \neq 0$, there exists $q$ and $r \in R$ such that

$$
a = bq + r
$$

where either

$$
r = 0
$$

or

$$
N(r) < N(b)
$$

In such cases, $q$ is called quotient, $r$ is called the remainder.

:::

這個 *norm* 只要存在就好。這邊要模擬的性質其實就像是輾轉相除法，因為餘數會越來越小，而且 *norm* 又是在非負整數中，所以這個輾轉相除就會有終結的一天。某些程度來說就是一個有輾轉相除法的 *integral domain*，所以那些因為輾轉相除法而有的性質，在這上面也都有，所以也可以談像最大公因數之類的概念。

比如說這樣就可以在 $\Bbb Z[i]$ 上面談最大公因數 (雖然做起來很怪)。

舉例來說，考慮實係數多項式：

$$
\begin{align}
N : \Bbb R[x] & \to \Bbb Z^+ \cup \{0\}
\newline
f(x) & \mapsto \deg f(x)
\end{align}
$$

這個函數 (取最高次數) 會是一個 *norm*，所以就可以做輾轉相除法：

$$
a = bq_0 + r_0 \Rightarrow b = q_1 r_0 + r_1
$$

其中：

$$
N(r_1) < N(r_0) < N(b)
$$

因為 $N(r_i) < N(r_j)$ $\forall i < j$，所以總有一天都會終結。

### 例子：Z[i]

假定有兩個 $\Bbb Z[i]$ 中的複數：

$$
\begin{align}
\alpha = a + bi
\newline
\beta = c + di
\end{align}
$$

其中，$a, b, c, d \in \Bbb Z$，他們做複數的除法：

$$
x = \frac {\alpha}{\beta} = \frac {ac + bd}{c^2 + d^2} + \frac {ad + bc}{c^2 + d^2}i
$$

接下來要找 $q$。這個 $q$ 要滿足：

$$
\frac {N(r)}{N(b)} < 1
$$

假定 $x$ 被包含在某個格子中。$x$ 距離所屬的格子中的四個點最大的距離，不超過 $\frac {\sqrt 2}{2}$。令：$x$ 所屬的格子的 $4$ 個頂點中，離 $x$ 最近的那個點是 $q_0$。也就是：

$$
\exists q_0 \in \Bbb Z[i]. \left\lvert \frac {\alpha}{\beta} - q_0\right\rvert \leq \frac {\sqrt{2}}{2}
$$

其中：

$$
|a + b_i| = \sqrt{a^2 + b^2} = \sqrt{N(a + bi)}
$$

這時候就定義 $r_0$ 為：

$$
r_0 = \alpha - \beta q_0
$$

假定 $r_0 = 0$，那麼這個 $q_0$ 就是格子點。接下來檢驗 *norm* 有沒有嚴格比 $N(b)$ 小。可以觀察：這個 *norm* 現在有下面的性質：

$$
N(\alpha \beta) = N(\alpha)N(\beta)
$$

且：

$$
N(x) = 0 \iff x = 0
$$

可以驗證：若 $r_0 \neq 0$，則 $N(r_0) < N(\beta)$。只要驗證：

$$
\frac {N(r_0)}{N(\beta)} < 1
$$

就可以了，可是這個東西就是：

$$
\frac {N(r_0)}{N(\beta)} = N \left(\frac {r_0}{\beta}\right) = \underbrace{N\left(\frac {\alpha}{\beta} - q_0\right)}_{\leq \frac{\sqrt 2}{2} < 1}
$$

因此就證明了這個上面有除法。

## 觀察：ED 裡面的 Ideal 可以被 Norm 最小的非零元素生成

:::danger

假定 $R$ 是個 *Euclidean Domain*，且 $I \unlhd R$。假定 $N$ 是一個 *Euclidean Domain* 的 *norm*，且 $d \in I$。若 $d$ 是 $I$ 中其中一個 *norm* 最小的非零元素，即：

$$
N(d) = \min_{0 \neq x \in I}N(x)
$$

則 $d$ 可以生成 $I$：

$$
(d) = I
$$

:::

這個跟證明「所有循環群的子群都是循環的」有點像。

假定 $N$ 是那個 *norm*，$R$ 是一個 *Euclidean domain*。假定 $I = \{0\}$，這個就沒有什麼好證明。假定：

$$
0 \neq I \lhd R
$$

找出 $I$ 當中 *norm* 最小的非零元素，假定它叫做 $d$。也就是：

$$
\exists d \in I.N(d) = \min_{0 \neq x \in I}N(x)
$$

這時用除法：

$$
\begin{align}
&\forall a \in I.\exists q, r \in R.
\newline
& a = qd + r \quad r = 0 \text{ or }N(r) < N(d)
\end{align}
$$

可以觀察：$r$ 要在 $I$ 裡面：

$$
r = a - qd \in I
$$

因為 $N(d)$ 已經是最小的 *norm* 了，所以不可能有 $N(r)<N(d)$。只能有 $r=0$，所以

$$
\begin{align}
&r = 0
\newline
&\Rightarrow a = q d \in (d)
\newline
&\Rightarrow I = (d)
\end{align}
$$

## 觀察：Euclidean 中的 Ideal 都是 Principal Ideal

:::danger

Every ideal in a Euclidean Domain is principal

:::

這是一個 *Euclidean Domain* 的必要條件，所以可以拿來幫助證明一個東西不是 *Euclidean Domain*。不然照定義要證明這樣的 *norm* 不存在實在是太困難了。

### 例子：證明不是 Euclidean Domain

$\Bbb Z[x]$ 中， $(p, x)$ 不是一個 *principal ideal*。因為假定：

$$
(p, x) = (\alpha)
$$

就會發現：

$$
\begin{align}
&\alpha \mid p \text{ and }\alpha \mid x
\newline
&\Rightarrow x = 1 \text{ or }p\ (\text{but }p \not \mid x) \newline
&\Rightarrow x = 1
\end{align}
$$

### 例子：另外一個不是 Euclidean Domain 的例子

考慮 $\Bbb Z + \Bbb Z[\sqrt{-5}]$，他不是 *Euclidean Domain*，因為下面這個 *ideal* 不是 *principal ideal*：

$$
I = (3, 2 + \sqrt{-5})
$$

證明方法就是反證法：假定 $I = (\alpha)$。這時候：

$$
3 = \alpha \cdot x \Rightarrow \underbrace{N(3)}_{9} = N(\alpha)N(x)
$$

類似地：

$$
2 + \sqrt{-5} = \alpha \cdot y \Rightarrow \underbrace{N(2 + \sqrt{-5})}_{9} = N(\alpha)N(y)
$$

因此：

$$
N(\alpha) \mid 9 \Rightarrow N(\alpha) = 1, 3, 9
$$

1. 第一個狀況是 $1$。這時候會發現 $\alpha = a + bi$ 必須滿足：

$$
a^2 + 5b^2 = 1
$$

這時候 $\alpha$ 只能是 $\pm 1$。由 *Quadric Integer* 的 *Norm* 知道 $N(\alpha) = 1$ 充分必要於 $\alpha$ 是個 *unit*，這時候就會發現 $I$ 就是整個 $\Bbb Z + \Bbb Z[\sqrt{-5}]$。但是可以證明這個 *ideal* 不是全部，因為假定他是全部，這就表示 $1 \in I = R$，這時候由 $(3, 2 + \sqrt{5})$ 的定義：

$$
1 = 3x + (2 + \sqrt{-5})y
$$

但這就表示：

$$
(2 - \sqrt{-5}) = 3(2 - \sqrt{-5}x) + 9y \Rightarrow 3 \mid 2 - \sqrt{5}
$$

就矛盾了。

2. 第二個狀況：

$$
N(\alpha) = a^2 + 5b^2 = 3
$$

這個東西沒有整數解。

3. 第三個狀況：

$$
N(\alpha) = a^2 + 5b^2 = 9
$$

這時候可以發現：

$$
N(3) = 9 = \underbrace{N(\alpha)}_{9}N(x)
$$

所以

$$
N(x) = 1 \Rightarrow x = \pm 1
$$

帶回：

$$
3 = \pm \alpha \Rightarrow \alpha = \pm 3
$$

所以 $\alpha$ 要是 $\pm 3$ 裡面其中一個。可是這樣問題就來了，因為對 $(2 - \sqrt{-5})$ 做一模一樣的事：

$$
\underbrace{N(2 + \sqrt{-5})}_{9} = \underbrace{N(\alpha)}_{9}N(y)
$$

就會發現：

$$
N(y) = 1 \Rightarrow y = \pm 1
$$

因此會得到 $\alpha$ 也要是：

$$
\alpha = \pm(2 + \sqrt{-5})
$$

但這很顯然是個矛盾，因為 $\alpha$ 不可能既是 $\pm 3$ 的其中一個，又是 $\pm(2 + \sqrt{-5})$ 裡面其中一個。顯然 $2 + \sqrt{-5} \not \in (3)$。另外一方面，$3 \not \in (2 + \sqrt{5})$。因為假定存在 $c, d \in \Bbb Z$，使得：

$$
(c + d\sqrt{-5})(2 + \sqrt{-5}) = 3
$$

那麼就有：

$$
(2c - 5d) + (c + 2d)\sqrt{5} = 3
$$

但這樣一來就沒有整數解：

$$
c = -2d \Rightarrow -9d = 3 (\rightarrow\leftarrow)
$$