7.1 整除、最大公因數與整數方程

為何整數算術需要新的語言

整數算術看似熟悉，但要證明關於整數的命題，不能只沿用實數除法的直覺。在實數代數中，$a/b$ 通常是一個合法的實數；在整數論中，更重要的問題是：這個商能否仍然是一個整數？

這個問題會支撐後面的很多方法。它讓我們定義質數、描述共同因子、有效計算最大公因數，並判斷

$$ax+by=c$$

是否有整數解。

整除

定義中的「存在整數」是重點。例如 $3\mid 15$，因為 $15=3\cdot5$；但 $4\nmid 15$，因為不存在整數 d 使 $15=4d$。

幾個邊界情況要先說清楚：

• 任意整數都整除 0，因為 $0=a\cdot0$；
• 0 只整除 0，因為 $x=0\cdot d$ 會迫使 $x=0$；
• $\pm1$ 整除所有整數；
• 若 $a\ne0$，則 a 和 $-a$ 都整除 a。

第四條是後面經常使用的工具：若一個整數同時整除兩個數，它也會整除這兩個數的任意整數線性組合。例如 $6\mid 18$ 且 $6\mid 30$，所以

$$6\mid 18x+30y$$

對所有整數 x,y 都成立。

質數、合數與良序原理

等價地，$n>1$ 是合數，正是指存在整數 $n_1,n_2$ 滿足

$$n=n_1n_2,\qquad 1<n_1,n_2<n.$$

關於質數的證明常常依賴以下次序事實。

良序原理讓我們可以使用「最小反例」論證。若某類壞整數非空，選出其中最小的一個，再證明它會產生更小的壞整數，便得到矛盾。

證明思路如下。假設結論錯誤，令 m 是最小的、大於 1 但沒有質因數的整數。m 不可能本身是質數，所以 $m=n_1n_2$，其中 $1<n_1,n_2<m$。由 m 的最小性，較小的 $n_1$ 有質因數 p。又因為 $p\mid n_1$ 且 $n_1\mid m$，所以 $p\mid m$，矛盾。

若質數只有有限多個 $p_1,\ldots,p_N$，考慮

$$n=p_1p_2\cdots p_N+1.$$

上一個定理保證 n 有某個質因數。這個質因數必須是列表中的某個 $p_i$。但 $p_i$ 亦整除乘積 $p_1p_2\cdots p_N$，所以它整除差

$$n-p_1p_2\cdots p_N=1,$$

這不可能。

最大公因數

當輸入不全為零時，最大值存在，因為共同因數的絕對值受到限制。除了 $a=b=0$ 的特殊情況外，$\gcd(a,b)$ 都是正整數。

最大公因數可用來移除兩個整數的共同部分。若

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

則

$$\gcd\left(\frac ad,\frac bd\right)=1.$$

例如 $\gcd(126,140)=14$，所以

$$\frac{126}{140}=\frac{9}{10},$$

而 9 與 10 互質。

除法算法

接下來的問題是計算性的：若不能事先列出所有共同因數，怎樣求最大公因數？關鍵是帶有受控餘數的整數除法。

條件 $0\le r<|b|$ 不是附加裝飾，而是唯一性的核心。例如

$$17=5\cdot3+2$$

符合除法算法；但

$$17=5\cdot2+7$$

不符合，因為餘數 7 不小於 5。

最大公因數不變性與歐幾里得算法

除法算法有用，是因為把 (a,b) 換成 (b,r) 不會改變最大公因數。

理由是：a,b 的共同因數會整除 $r=a-bq$；反過來，b,r 的共同因數會整除 $a=bq+r$。因此兩對數的正共同因數完全相同。

算法必然停止，因為餘數形成嚴格遞減的非負整數列：

$$r_1>r_2>r_3>\cdots\ge0.$$

非負整數不可能無限地嚴格遞減。

擴展歐幾里得算法與 Bézout 恆等式

同一個計算可以倒推，將最大公因數寫成原本兩個數的整數線性組合。

這個結果說明，最大公因數不只是最大的共同因數；它也可以由 a,b 的整數線性組合產生。

若 $\gcd(a,b)=1$，這就是 Bézout 恆等式。反過來，若 $ax+by=1$，任何共同因數都必須整除 1，所以最大正共同因數只能是 1。

共同因數與 Euclid 引理

Bézout 恆等式也給出最大公因數的另一個重要刻畫。

正向尤其有用。若 n 同時整除 a 和 b，則 n 整除任意線性組合 $ax+by$；特別地，它整除等於 $\gcd(a,b)$ 的 Bézout 線性組合。

若 $p\nmid a$，則 $\gcd(a,p)=1$，所以存在整數 m,n 使

$$am+pn=1.$$

兩邊乘以 b 得

$$abm+pbn=b.$$

因為 $p\mid ab$，左邊兩項都被 p 整除，所以 $p\mid b$。

唯一質因數分解

存在性仍然來自最小反例法。若存在最小的、大於 1 且不能寫成質數乘積的整數，它不可能是質數，因此可分解成兩個更小的因數；但這兩個較小因數已經可以分解成質數乘積，矛盾。

唯一性使用 Euclid 引理。若

$$p_1p_2\cdots p_r=q_1q_2\cdots q_s,$$

則 $p_1$ 整除右邊乘積，所以 $p_1$ 必整除某個質因數 $q_j$，從而 $p_1=q_j$。消去後重複同樣論證。

這個定理也給出計算最大公因數的指數方法。若

$$a=p_1^{m_1}\cdots p_r^{m_r}, \qquad b=p_1^{n_1}\cdots p_r^{n_r},$$

其中缺少的質數用指數 0 補上，則

$$\gcd(a,b)=p_1^{\min(m_1,n_1)}\cdots p_r^{\min(m_r,n_r)}.$$

一次 Diophantine 方程

未知數 x,y 必須是整數的方程

$$ax+by=c$$

稱為一次 Diophantine 方程。Bézout 恆等式可以完全判定它何時有解。

若解存在，因為 d 整除 a,b，所以 d 整除 $ax+by=c$。反過來，若 $c=dr$，由 Bézout 恆等式有 $d=am+bn$，因此

$$c=dr=a(mr)+b(nr).$$

所以 (mr,nr) 是一組解。

若已知一組解，也可以描述所有解。設 $d=\gcd(a,b)\ne0$，並令

$$u=\frac ad,\qquad v=\frac bd.$$

若 $(x_0,y_0)$ 是一組解，則所有解為

$$x=x_0+kv,\qquad y=y_0-ku,\qquad k\in\mathbb Z.$$

快速檢查

練習

1. 列出 84 的所有正因數，並求 $\gcd(84,60)$。
2. 用除法算法把 $-37$ 寫成 $-37=5q+r$，其中 $0\le r<5$。
3. 用歐幾里得算法求 $\gcd(252,198)$。
4. 將 $\gcd(252,198)$ 寫成 $252x+198y$。
5. 證明：若 $n\mid a$ 且 $n\mid b$，則 $n\mid\gcd(a,b)$。
6. 判斷 $35x+21y=14$ 是否有整數解；若有，求一組解。
7. 判斷 $35x+21y=10$ 是否有整數解。
8. 用質因數分解求 $\gcd(2^4\cdot3^2\cdot5,\, 2^3\cdot3^5\cdot7)$。