代數入門 - 第1章第5節：初等整數論

代數入門

第1章 數的演化

5. 初等整數論

0 與自然數（正整數）是連小學一年級生都能理解的簡單數字，小學的算術課也花了許多時間在它們的計算練習上。

然而，若從探究整數內部規律性的立場來看，我們會發現其中隱藏著令人驚訝的奇妙法則。探究潛藏於整數中法則的學問稱為整數論，接下來我們將 briefly 闡述其初步內容。

如前所述，整數集合對於 +, -, × 這三種運算是封閉的，但對於 ÷ 則不是。例如，$2 \div 3$ 的答案不會是整數。事實上，整數論的切入點就在於此。

5.1 約數

當 $b \div a$ ($a>0$) 的答案是整數時，我們說 b 可被 a 整除。此時，b 稱為 a 的倍數，a 稱為 b 的約數。

一般而言，當 b 除以 a 時，若商為 q，餘數為 r，則：

$b = qa + r \quad (0 \le r < a)$

當 b 不為負數時，這可以圖示如下，表示 b 可以寫成這種形式。

當此時的餘數為 0 時，b 就被 a 整除。

我們用 $Y(a)$ 來表示正整數 a 的所有正約數的集合。

例如：

$Y(1) = \{1\}$

$Y(2) = \{1, 2\}$

$Y(3) = \{1, 3\}$

$Y(4) = \{1, 2, 4\}$

$Y(5) = \{1, 5\}$

a 的約數不會超過 a，因此這些當然是有限集合。

兩個正整數 a, b 的共同正約數稱為公約數。用集合的符號來寫，a 與 b 的正公約數集合是 a 的約數集合 $Y(a)$ 與 b 的約數集合 $Y(b)$ 的交集：

$Y(a) \cap Y(b)$

例如，8 與 12：

$Y(8) = \{1, 2, 4, 8\}$

$Y(12) = \{1, 2, 3, 4, 6, 12\}$

其交集為：

$Y(8) \cap Y(12) = \{1, 2, 4\}$

這與 4 的約數集合 $Y(4)$ 是相同的。

圖1-5

輾轉相除法

公約數的集合是有限集合，因此其中必有最大的一個，稱為 a, b 的最大公約數，以 $(a, b)$ 表示。顯然 $(a, b) = (b, a)$。

定理1： 若 $b > a$，則 $(a, b-a) = (a, b)$

證明：

設 c 是 a, b 的公約數，則 $a=a'c, b=b'c$ (a', b' 為整數)。 $b-a = b'c - a'c = (b'-a')c$，因此 c 也是 b-a 的約數，也就是說，c 是 a, b-a 的公約數。

反之，設 d 是 b-a 和 a 的公約數，則 $b-a=ed, a=fd$。 $b = (b-a) + a = ed + fd = (e+f)d$，因此 d 也是 b, a 的公約數。

也就是說，a, b 的公約數集合與 a, b-a 的公約數集合完全相同。因此，a, b 的最大公約數應與 a, b-a 的最大公約數相等。即

$(a, b) = (a, b-a)$

(證明完)

連續使用以上結論，可得：

$(a, b) = (a, b-a) = (a, b-2a) = \dots = (a, b-qa)$

又因為 b 可表示為 $b = qa + r$ ($0 \le r < a$)，所以 $r = b-qa$。因此：

$(a, b) = (a, r) \quad (0 \le r < a)$

也就是說，a, b 的最大公約數 $(a, b)$ 等於 b 除以 a 的餘數 r 與除數 a 的最大公約數 $(a, r)$。

接著，再用 r 來除 a：

$a = q_1 r + r_1 \quad (0 \le r_1 < r)$

可得

$(a, r) = (r_1, r) \quad (0 \le r_1 < r)$

如此不斷地用餘數去除前一個餘數，餘數會 $r > r_1 > r_2 > \dots$ 這樣逐漸變小，最終會變為 0。

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

此時最後一個非零的餘數 $r_n$ 就是 $(a, b)$ 的最大公約數。這種求最大公約數的方法稱為輾轉相除法。這個方法自古希臘時代就已為人所知。

例題1

用輾轉相除法求 (39, 90)。

2
39 ) 90
78
12

3
12 ) 39
36
3

4
3 ) 12
12
0

解：因此 (39, 90) = 3

這種方法，比起後面要講的質因數分解法，因為不利用質數，所以在原理上更為單純。

問

用輾轉相除法求下列各組數的最大公約數。

(32, 48), (52, 84), (63, 91), (204, 512)

5.2 質數

一個正整數若正好有 2 個正約數，則稱之為質數。例如：

$Y(2) = \{1, 2\}$

$Y(3) = \{1, 3\}$

$Y(5) = \{1, 5\}$

因此 2, 3, 5, ... 是質數。然而：

$Y(1) = \{1\}$

所以 1 不是質數。

有一種簡單而樸素的方法可以找出質數，那就是將非質數篩選掉的方法。我們從 1 開始依序寫下正整數，並在其下方留出空位。

步驟 1：列出數字

1	2	3	4	5	6	7	8	9	10	11	12	13
14	15	16	17	18	19	20	21	22	23	24	25	...

首先，1 不是質數，其下方的空位保持空白。接下來的 2，除了 1 和 2 之外沒有其他約數，所以是質數，其下方的空位也保持空白。

接著，在 2 的倍數 4, 6, 8, ... 下方的空位中寫入 2。

步驟 2：篩掉 2 的倍數

1	2	3	4	5	6	7	8	9	10	11	12	13
			2		2		2		2		2
14	15	16	17	18	19	20	21	22	23	24	25	...
2		2		2		2		2		2

因此，被寫入 2 的數字就不再是質數了。在 2 之後剩下的數字是 3，而 3 不能被 2 整除，所以是下一個質數。我們將 3 的下方留白，然後在 3 的倍數 6, 9, 12, 15, 18, ... 下方的空位寫入 3。

步驟 3：篩掉 3 的倍數

1	2	3	4	5	6	7	8	9	10	11	12	13
			2		2		2	3	2		2
14	15	16	17	18	19	20	21	22	23	24	25	...
2	3	2		2		2	3	2		2

不過，像 6, 12, 18, ... 的下方已經寫有 2，就保持原樣，只在 9, 15, 21, ... 的下方寫入 3。

此時剩下的數中最小的是 5，而 5 不能被比它小的數（$\ne 1$）整除，所以是下一個質數。於是我們再次將 5 的下方留白，並在其倍數下方寫入 5。

步驟 4：篩掉 5 的倍數

1	2	3	4	5	6	7	8	9	10	11	12	13
			2		2		2	3	2		2
14	15	16	17	18	19	20	21	22	23	24	25	...
2	3	2		2		2	3	2		2	5

持續這個方法，就可以找出任意範圍內的質數。這種將非質數篩選掉的方法，由古希臘人埃拉托斯特尼（Eratosthenes, B.C. 275-194）發現，因此被稱為「埃拉托斯特尼篩法」。

此外，下方空位中被填入的數字，正好是上方數字的最小質因數。因此，這個表也可以稱為約數表。在平山諦的《東西數學物語》（恒星社厚生閣）書末附有 1 到 10 萬的約數表。

5.3 質因數分解

所有大於等於 2 的整數都擁有 1 和它本身作為約數（因數），而質數除了這兩個特殊的約數外，沒有其他約數。非質數的數則擁有 1 和它本身以外的約數。如果那個約數不是質數，就再找出它的約數，繼續分解下去。持續這個過程，任何數應該都能被寫成質數的乘積。

定理2： 所有正整數都可以表示為質數的乘積。

將整數分解為質數的乘積，稱為質因數分解。要具體計算，前面製作的約數表就很有用。

例題2

將 18 進行質因數分解。

解：查約數表，18 下方的數字是 2，所以 2 是最小的質因數。用 2 去除 18，得到 9。9 下方的數字是 3，再用 3 去除 9，商 3 是質數，所以到此為止。

2 ) 18
3 )  9
3

也就是說，$18 = 2 \cdot 3 \cdot 3 = 2 \cdot 3^2$

問

製作 1 到 100 的約數表，並用它將 1 到 100 的數字進行質因數分解。

如上所述，所有整數都可以被質因數分解，但分解的方式只有一種嗎？還是有好幾種呢？要確認這一點是個稍微困難的問題，需要一些準備。

5.4 數學歸納法

作為準備之一，我們先說明一下數學歸納法。例如，考慮這樣一個陳述：「從 1 開始，將 n（正整數）個奇數依序相加，答案會是 n 的平方」。這個陳述也可稱為主張或命題。

這個主張是否對所有的 n 都正確，目前還不知道。無論如何，這是一個在陳述中包含 n 的主張，所以我們將它寫作 S(n)。S(n) 不僅限於用普通文章寫成的東西，也可以是用符號表示的數學式。這個 S(n) 的主張是否對所有的 n 都正確，目前還不清楚。但是，假設有人預測 S(n) 這個主張對所有的 n 似乎都是真的，並打算證明它。這時，他可以使用的一種方法就是數學歸納法。

它是這樣的：如果他能證明以下兩件事，那麼他就達成了目標。

1. (A) S(1) 是真的。
2. (B) 當 $n \ge 1$ 時，若 S(n) 是真的，則 S(n+1) 也是真的。

如果以上的 (A) 和 (B) 都被證明了，那麼 S(n) 對於所有的 n 都會是真的。

這很像骨牌遊戲。

圖1-6

假設 S(1), S(2), ... 像骨牌一樣排列著。在這裡，假設骨牌的排列方式是：當 $n \ge 1$ 時，如果前面的 S(n) 倒下，那麼下一個 S(n+1) 也會倒下 [即 (B)]。只要推倒第一個 S(1) [即 (A)]，根據 (B) 當 $n=1$ 時，因為前面的 S(1) 倒了，所以 S(2) 也會倒。接著根據 (B) 當 $n=2$ 時，因為前面的 S(2) 倒了，所以 S(3) 也會倒。依此類推，S(4), S(5), ... 所有的骨牌應該都會倒下。

在這裡，如果將「S(n) 倒下」替換為「S(n) 是真的」，就完全變成了數學歸納法。把數學歸納法想成「骨牌推論法」，就很容易記住了。

這種論法的威力在於，透過假設 S(n) 是真的（儘管尚未證明），並證明 S(n+1) 也是真的，就可以證明所有的 S(n) 都是真的。(B) 中的 S(n) 有時被稱為「歸納假設」。

然而，在提出「S(n) 似乎是真的」這個猜想的階段，這種論法不太有用。提出猜想通常是透過其他方法。

讓我們用數學歸納法來證明最開始提到的命題。

(A) 當 $n=1$ 時：$1 = 1^2$，因此 S(1) 是真的。

(B) 假設 S(n) 是真的，即：

$\underbrace{1 + 3 + \dots + (2n-1)}_{n \text{個}} = n^2$

是正確的。如果在兩邊加上下一個奇數 $2n+1$：

$1 + 3 + \dots + (2n-1) + (2n+1) = n^2 + (2n+1) = (n+1)^2$

這樣一來，S(n+1) 也變成是真的了。

這樣，數學歸納法該證明的都完成了。因此，我們知道了 S(n) 對於所有的 n 都是真的。

回顧一下「骨牌推論法」，可以發現即使將 (B) 稍微改變成以下形式，數學歸納法仍然適用。

1. (A) S(1) 是真的。
2. (B') 如果 S(1), S(2), ..., S(n) 都是真的，那麼 S(n+1) 也是真的。

5.5 質因數分解的唯一性

現在，讓我們用數學歸納法來證明質因數分解的唯一性。

定理3： 對於三個整數 a, b, c，若 $(a, b) = 1$ 且 bc 可被 a 整除，則 c 可被 a 整除。

證明：

將此主張寫作 S(a)，並用關於 a 的數學歸納法來證明。

(A) 當 a=1 時，對於任意的 b, c 當然都成立。

(B) 假設 S(1), S(2), ..., S(a-1) 這個命題都為真。

根據命題 S(a) 的假設，$(a, b) = 1$ 且 a 整除 bc。現在用 a 去除 b：

$b = qa + r \quad (0 \le r < a)$

則

$1 = (b, a) = (qa+r, a) = (r, a)$

$bc = (qa+r)c = qac + rc$

$rc = bc - qac$

因為 bc 可被 a 整除，qac 當然也可被 a 整除，所以它們的差 rc 也可被 a 整除。因此可寫成：

$rc = ad \quad \text{(d 為整數)} \quad (1)$

因為 $r \le a-1$ 且 $(r, a) = (b, a) = 1$，又 ad 可被 r 整除，根據歸納假設 S(r) 為真，也就是 d 可被 r 整除。即：

$re = d \quad \text{(e 為整數)}$

將此代入 (1) 式：

$rc = are$

約掉 r，得到：

$c = ae$

也就是說 c 可被 a 整除，即 S(a) 為真。因此，這個命題對所有的 a 都成立。(證明完)

定理4： 若兩個整數的乘積 ab 可被質數 p 整除，則因數 a 或 b 之中必有一個可被 p 整除。

證明：

$(a, p)$ 是 p 的約數，因此 $(a, p) = 1$ 或 p。

若 $(a, p) = 1$，根據定理3，p 整除 b。

若 $(a, p) = p$，則顯然 p 整除 a。(證明完)

這個定理可以輕易地擴展到多個因數的情況。也就是說：

「若乘積 $abc \dots l$ 可被質數 p 整除，則因數 $a, b, c, \dots, l$ 中必有某一個可被 p 整除。因此，若因數 $a, b, c, \dots, l$ 中沒有一個可被 p 整除，則乘積 $abc \dots l$ 也不可被 p 整除。」

利用這個定理，可以證明質因數分解的唯一性。

定理5 (質因數分解的唯一性)： 正整數的質因數分解方式只有一種。

證明：

假設正整數 a 被分解為質因數 $p_1, p_2, \dots, p_n$。為了證明的方便，我們先規定 $p_1 \ge p_2 \ge \dots \ge p_n$。

$a = p_1 p_2 p_3 \dots p_n$

假設 a 還有另一種質因數分解的形式：

$a = q_1 q_2 \dots q_m \quad (q_1 \ge q_2 \ge \dots \ge q_m)$

此時，如果能證明 $m=n$ 且 $p_1=q_1, p_2=q_2, \dots, p_n=q_n$，那麼證明就完成了。

假設情況並非如此，那麼必定存在第一個使得 $p_k \ne q_k$ 的序號 k。在此之前的序號，當然是 $p_1=q_1, p_2=q_2, \dots, p_{k-1}=q_{k-1}$。

$a = p_1 \dots p_{k-1} p_k \dots p_n = q_1 \dots q_{k-1} q_k \dots q_m$

因為 $p_1=q_1, \dots, p_{k-1}=q_{k-1}$，兩邊同除後得：

$p_k p_{k+1} \dots p_n = q_k q_{k+1} \dots q_m \quad (1)$

我們假設 $p_k > q_k$。因為 $p_k > q_k \ge q_{k+1} \ge \dots \ge q_m$。

從 (1) 式可知，$q_k q_{k+1} \dots q_m$ 可被 $p_k$ 整除。然而，由於 $(p_k, q_k) = 1$，根據定理3，$q_{k+1} \dots q_m$ 必須被 $p_k$ 整除。又因為 $(p_k, q_{k+1}) = 1$，用同樣的推論，$q_{k+2} \dots q_m$ 也必須被 $p_k$ 整除。持續這個推論，最後的 $q_m$ 也必須被 $p_k$ 整除。但這顯然不可能，因為 $p_k > q_m$。

因此，使得 $p_k \ne q_k$ 的序號 k 不可能存在。所以：

$p_1=q_1, p_2=q_2, \dots, p_n=q_n \quad (n=m)$

唯一性得證。

最初我們假設 $p_k > q_k$，若是 $p_k < q_k$ 的情況，只需將 p 和 q 互換即可。(證明完)

這個唯一性定理通常在不加證明的狀況下被使用，但既然是數學，最好還是在使用前先加以證明。

另外，在上面的證明中，我們透過否定待證結論「$p_1=q_1, \dots$」而導出矛盾「$q_m$ 可被 $p_k$ 整除」，一般來說，像這樣透過否定結論來導出矛盾，藉以證明命題的方法，稱為反證法（或稱歸謬法）。