The Ring of Integers

整數中最基本的定理應該就是整數的餘數定理 Euclid's Algorithm, 幾乎所有整數的基本性質都是由它推導出來的. 其實我們在前面已經用過這個定理好幾次了, 不過為了完整性我們還是給一個證明.

証明. 這個定理我們習慣稱為餘數定理, 如此稱它當然就包含``除''這個概念. 不過因為我們畢b在談 ring 的性質, 我們避免用除的概念.

首先考� W = {m - t^.n | t $\in$ $\mathbb {Z}$ } 這一個集合. 因為 t 可取任何整數, 很容易就看出 W 一定包含一些非負的整數. 令 r 是 W 中最小的非負的整數, 因為 r $\in$ W, 由定義知存在 h $\in$ $\mathbb {Z}$ 滿足 r = m - h^.n. 我們最主要的目的就是要證明 0 $\le$ r < n.

假設 r 不合我們的條件, 也就是說 r $\ge$ n (別忘了 r 是非負整數的假設). 若如此, 我們可將 r 寫成 r = n + r', 其中 r' $\ge$ 0. 因此利用

m = h^.n + r = h^.n + (n + r') = (h + 1)^.n + r',

我們得到 r' = m - (h + 1)^.n $\in$ W. 但 0 $\le$ r' < r, 這和 r 是 W 中最小的非負整數相矛盾. 故得證本定理. $\qedsymbol$

要注意 Theorem 7.1.1 的證明我們用到整數上可以排序的 well-ordering principle, 因此雖然證明很簡單, 但並不能直接套用到一般的 ring. 也就是說, 一般的 ring 不一定有所謂的 Euclid's Algorithm. 將來我們會看到一些特殊的 integral domain 也有所謂的 Euclid's Algorithm. 這樣的 integral domain 我們會給它一個名稱: 稱為 Euclidean domain.

証明. 複習一下定義: 若 I 是一個 $\mathbb {Z}$ 的 ideal, 我們想說在 I 中存在一元素 a 使得

I = $\displaystyle \bigl($ a $\displaystyle \bigr)$ = {h^.a | h $\displaystyle \in$ $\displaystyle \mathbb {Z}$ },

也就是說 I 是所有 a 的倍數所成的集合. 若已知ㄧ集合是由某數的所有倍數所成的集合, 你要怎麼找出這個數呢? 當然是找其中最小的正整數了!

$\mathbb {Z}$ 中的 trivial ideal Z 和 {0}, 分別由 1 和 0 生成, 所以都是 principle ideal. 因此我們只要考� $\mathbb {Z}$ 中 nontrivial proper ideal 就可. 假設 I 是 $\mathbb {Z}$ 的一個 nontrivial proper ideal, 由於 I $\ne$ {0}, 故存在 b $\ne$ 0, 且 b $\in$ I. 由於 I 是 ideal, - b 也在 I 中, 因此我們知 I 中必存在正整數. 畦O a $\in$ I 是 I 中最小的正整數, 我們要證明 I = $\bigl($ a $\bigr)$ .

首先 a $\in$ I, 所以對任意的 h $\in$ $\mathbb {Z}$ 皆有 h^.a $\in$ I, 故知 $\bigl($ a $\bigr)$ $\subseteq$ I. 因此我們僅剩下要證 I $\subseteq$ $\bigl($ a $\bigr)$ , 換句話就是要證明 I 中的元素都是 a 的倍數. 任取 m $\in$ I 怎麼說 m 是 a 的倍數呢? (當然就是拿 m 除以 a 看看餘數是什麼了.) 利用 Theorem 7.1.1, 我們知存在 h, r $\in$ $\mathbb {Z}$ , 0 $\le$ r < a 滿足 r = m - h^.a. 由於 m $\in$ I 且 h^.a $\in$ I, 利用 I 是 ideal 知 r = m - h^.a $\in$ I. 但已知 a 是 I 中最小的正整數, 故得 r = 0, 即 m = h^.a $\in$ $\bigl($ a $\bigr)$ . 也就是說 I $\subseteq$ $\bigl($ a $\bigr)$ . $\qedsymbol$

我們曾提醒過, 並不是所有的 ring 它的 ideal 都會是 principle ideal. 如果一個 integral domain 它的 ideal 都是 principle ideal, 這樣特別的 integral domain 我們稱之為 principle ideal domain. 注意以上 $\mathbb {Z}$ 是 principle ideal domain (Theorem 7.1.2) 的性質, 是由 $\mathbb {Z}$ 是 Euclidean domain (Theorem 7.1.1) 這個性質推導出來的.

這一節我們主要是談整數上元素的分解, 所以還是給因數, 公因數和最大公因數下一個定義.

Definition 7.1.3 令 a, b $\in$ $\mathbb {Z}$ .

若 d $\in$ $\mathbb {Z}$ 且存在 h $\in$ $\mathbb {Z}$ 使得 a = h^.d, 則稱 d 是 a 的一個 divisor, 記做 d | a.
若 c $\in$ $\mathbb {Z}$ , 且 c | a 及 c | b, 則稱 c 為 a, b 的 common divisor.
若 d $\in$ $\mathbb {Z}$ 是 a, b 最大的 common divisor, 則稱 d 為 a, b 的 greatest common divisor.

一般都是利用所謂的輾轉相除法將兩個數的 greatest common divisor 求出, 在這裡我們將利用 Theorem 7.1.2 找到 greatest common divisor 並得到其基本性質.

証明. 由 Lemma 6.2.1 我們知

$\displaystyle \bigl($ a $\displaystyle \bigr)$ + $\displaystyle \bigl($ b $\displaystyle \bigr)$ = {r^.a + s^.b | r, s $\displaystyle \in$ $\displaystyle \mathbb {Z}$ }

是 $\mathbb {Z}$ 的一個 ideal. 由 Theorem 7.1.2 知存在 d $\in$ $\mathbb {Z}$ 使得 $\bigl($ d $\bigr)$ = $\bigl($ a $\bigr)$ + $\bigl($ b $\bigr)$ . 在這裡我們可以要求 d 是正的, 這是因為 -1 是 $\mathbb {Z}$ 的 unit 故 Lemma 6.5.4 告訴我們 $\bigl($ d $\bigr)$ = $\bigl($ -d $\bigr)$ .

接著我們要證明這個 d $\in$ $\mathbb {N}$ 是 a, b 的 greatest common divisor. 首先當然是要證 d 是 a, b 的 common divisor. 然而因 a $\in$ $\bigl($ a $\bigr)$ $\subseteq$ $\bigl($ a $\bigr)$ + $\bigl($ b $\bigr)$ = $\bigl($ d $\bigr)$ , 故知存在 r $\in$ $\mathbb {Z}$ 使得 a = r^.d. 也就是說 d | a. 同理, 由 b $\in$ $\bigl($ d $\bigr)$ 可得 d | b. 故知 d 是 a, b 的 common divisor.

那為甚麼 d 會是 a, b 的 common divisor 中最大的呢? 由於 d $\in$ $\bigl($ d $\bigr)$ = $\bigl($ a $\bigr)$ + $\bigl($ b $\bigr)$ , 我們知道存在 m, n $\in$ $\mathbb {Z}$ 使得 d = m^.a + n^.b. 然而若 c 是 a, b 的 common divisor, 即 c | a 且 c | b, 知存在 r, s $\in$ $\mathbb {Z}$ 使得 a = r^.c 且 b = s^.c. 因此得

d = m^.(r^.c) + n^.(s^.c) = (m^.r + n^.s)^.c.

也就是說 c | d. 所以知 d 是所有 a, b 的 common divisor 中最大的. $\qedsymbol$

Proposition 7.1.4 不只告訴我們如何找到 greatest common divisor, 事實上在證明中我們也證得 greatest common divisor 的兩個重要性質.

接下來我們要談整數的分解中最基本的元素: 質數. 大家都知道一個質數 p 就是因數只有 1 和本身的數. 利用這個性質我們可得到若 p | a^.b 則 p | a 或 p | b 這個性質, 因此大家都會拿這兩種性質來判別一個數是否為質數. 不過在一般的 ring 這兩種性質是很不一樣的, 所以我們用不同的名字來稱呼.

很顯然這兩種定義是不一樣的, 不過下一個定理告訴我們在整數中這兩種定義的元素是相同的. 也因如此在整數中我們就統一稱之為質數 (prime).

証明. 首先我們證若 p 是 irreducible 則 p 是 prime. 也就是說假設已知 p 是 irreducible. 任取 p | a^.b 我們要證明: p | a 或 p | b. 然而 p | a^.b 表示存在 r $\in$ $\mathbb {Z}$ 使得 a^.b = r^.p. 如果 p | a 那麼就得到我們要證的, 所以我們只要討論 p $\nmid$ a 的情況. 此時我們考� p, a 的 greatest common divisor 令之為 d. 由於 d | p 故由 p 是 irreducible 的假設知 d = 1 或 d = p. 然而 d 不可能等於 p, 否則由 d 是 p, a 的 common divisor 知 p = d | a: 此和 p $\nmid$ a 矛盾. 因此知 d = 1, 由 Corollary 7.1.5 知存在 n, m $\in$ $\mathbb {Z}$ 滿足 1 = n^.p + m^.a. 等式兩邊乘上 b 得

b = (n^.b)^.p + m^.(a^.b) = (n^.b)^.p + m^.(r^.p) = (n^.b + m^.r)^.p,

所以 p | b.

反之, 若已知 p 是一個 prime element 我們要證明 p 是 irreducible. 也就是證明若 d | p, 則 d = ±1 或 d = ±p. 然而 d | p 表示存在 r $\in$ $\mathbb {Z}$ 滿足 p = d^.r, 也就是說 p | d^.r. 故由 p 是 prime 的假設, 我們得 p | d 或 p | r. 當 p | d 時, 由原先假設 d | p 知 d = ±p. 當 p | r 時, 表示存在 s $\in$ $\mathbb {Z}$ 滿足 r = s^.p. 故由 p = d^.r = d^.(s^.p) 得 d^.s = 1. 因 d, s $\in$ $\mathbb {Z}$ , 故 d^.s = 1 表示 d = ±1. $\qedsymbol$

最後我們來看整數最基本也最重要的唯一分解定理. 由於正整數和負整數的分解只差一個負號, 我們只需考憧蕪蒱⑩滷〞p.

Theorem 7.1.8 假設 a $\in$ $\mathbb {N}$ 且 a > 1, 則存在 p₁,..., p_r, 其中 p_i 是相異的 prime, 滿足

a = p₁^{n₁ ...}p_r^n_r, n_i $\displaystyle \in$ $\displaystyle \mathbb {N}$ , $\displaystyle \forall$ i $\displaystyle \in$ {1,..., r}.

如果 a 可以分解成另� 的形式 a = q₁^{m₁ ...}q_s^m_s, 其中 q_i 是相異的 prime, 則 r = s 且經過變換順序可得 p_i = q_i, n_i = m_i, $\forall$ i $\in$ {1,..., r}.

首先來看存在性: 簡單來說存在性就是要證明每一個大於 1 的整數都可以寫成有限多個(可以相同) prime 的乘積. 如果 a 本身是個 prime, 則 a = p₁ (即 r = 1, n₁ = 1), 得證存在性. 如果 a 不是 prime 呢? 由 Proposition 7.1.7 知 a 不是 irreducible, 也就是說存在 a₁, b₁ $\in$ $\mathbb {N}$ 且 a₁ $\ne$ 1, b₁ $\ne$ 1 滿足 a = a₁^.b₁. 接下來就是看 a₁, b₁ 是不是 prime 了. 如果其中有一個不是 prime, 我們就� 續分解下去直到得到 prime 為止. 這個過竣@定會停下來因為每次分解後得的數越來越小. 當然最後就可以將 a 寫成一些 prime 的乘積了. 這樣的證明方式, 相信大家會有一種說不清楚的感覺, 所以我們還是用比較數學的方法來證明. 當 a = 2 時由於 2 是 prime, 所以在這情況存在性是對的. 接著假設對所有介於 2 和 a - 1 的整數存在性是對的. 如果 a 是 prime, 那存在性自然成立, 如果 a 不是 prime, 則由 Proposition 7.1.7 知 a = a₁^.b₁ 其中 a₁, b₁ $\in$ $\mathbb {N}$ 且 1 < a₁ < a 及 1 < b₁ < a. 故利用歸納假設知 a₁ 和 b₁ 都可寫成有限多個 prime 的乘積, 所以得證 a 也可以寫成有限多個 prime 的乘積.

如果一個 integral domain 有和 $\mathbb {Z}$ 一樣每個元素都可以唯一寫成一些 irreducible element 的乘積的性質, 我們便稱此 integral domain 為一個 unique factorization domain.