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

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

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

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

$$ax+by=c$$

是否有整數解。

整除

定義

整除

設 $a,b\in\mathbb Z$。若存在整數 $d$ 使得

$$b=ad,$$

則稱 $a$ 整除 $b$，記作 $a\mid b$。此時 $a$ 稱為 $b$ 的因數或除數。

定義中的「存在整數」是重點。例如 $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$。

定理

基本整除規則

設 $a,b,c\in\mathbb Z$。

1. 若 $b\ne0$ 且 $a\mid b$，則 $|a|\le |b|$。
2. 若 $a\mid b$，則 $(\pm a)\mid(\pm b)$。
3. 若 $a\mid b$ 且 $b\mid c$，則 $a\mid c$。
4. 若 $a\mid b$ 且 $a\mid c$，則對任意 $x,y\in\mathbb Z$， $a\mid (bx+cy)$。

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

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

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

證明線性組合規則時，寫成 $b=am$、$c=an$，其中 $m,n$ 為整數。 於是 $bx+cy=a(mx+ny)$，新的乘數仍是整數。論證沒有除以 $a$， 因此即使 $a=0$ 也成立。

質數、合數與良序原理

定義

質數與合數

設 $n\in\mathbb Z^+$ 且 $n\gt 1$。

• 若 $n$ 的正因數只有 $1$ 和 $n$，則 $n$ 是質數；
• 若 $n$ 不是質數，則 $n$ 是合數。

整數 $1$ 既不是質數，也不是合數。

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

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

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

定理

良序原理

$\mathbb N=\{0,1,2,\ldots\}$ 的任意非空子集都有最小元素。

最小元素必須屬於集合，下界則不必。實數區間 $(0,1]$ 的下界是 $0$， 但沒有最小元素，因為每個成員 $x$ 都有更小的成員 $x/2$。也可由強歸納法 證明良序原理：若自然數子集沒有最小元素，它不能含 $0$；若它不含 $0,\ldots,n$，便不能含 $n+1$，否則後者就是最小元素。歸納可知該子集為空。

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

定理

大於 1 的整數都有質因數

每個大於 $1$ 的正整數都至少有一個質因數。

證明思路如下。假設結論錯誤，令 $m$ 是最小的、大於 $1$ 但沒有質因數的整數。$m$ 不可能本身是質數，所以 $m=n_1n_2$，其中 $1\lt n_1,n_2\lt 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\in\mathbb Z$。若 $a,b$ 不同時為零，定義

$$\gcd(a,b)=\max\{d\in\mathbb Z:d\mid a\text{ and }d\mid b\}.$$

若 $a=b=0$，則定義 $\gcd(0,0)=0$。

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

改變符號不影響整除，所以 $\gcd(a,b)=\gcd(|a|,|b|)$，特別地 $\gcd(a,0)=|a|$。$\gcd(0,0)=0$ 是獨立約定：每個正整數都整除兩個零， 此時沒有最大的正共同因數。

定義

互質

兩個非零整數 $a,b$ 若唯一的正共同因數是 $1$，則稱它們互質。等價地，

$$\gcd(a,b)=1.$$

當兩個整數不同時為零時，最大公因數可用來移除它們的共同部分。若

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

則

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

若 $e$ 是 $a/d,b/d$ 的正共同因數，則 $de$ 是 $a,b$ 的共同因數。 由 $d>0$ 的最大性，$de\le d$，所以 $e\le1$，只能是 $e=1$。 排除 $(0,0)$ 很必要，否則不能除以 $d$。

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

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

而 $9$ 與 $10$ 互質。

除法算法

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

定理

除法算法

設 $a,b\in\mathbb Z$ 且 $b\ne0$。則存在唯一整數 $q,r$ 使得

$$a=bq+r,\qquad 0\le r\lt|b|.$$

$q$ 稱為商，$r$ 稱為餘數。

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

$$17=5\cdot3+2$$

符合除法算法；但

$$17=5\cdot2+7$$

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

先證明存在性。設 $a\ge0$、$b>0$，考慮

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}.$$

因為 $a\in S$，良序原理給出最小成員 $r=a-bq$。若 $r\ge b$， 則 $r-b=a-b(q+1)$ 是更小的非負成員，矛盾。因此 $0\le r\lt b$。 若 $a\lt0$、$b>0$，則 $A=a+(-a)b=(-a)(b-1)$ 非負。 用已證情形寫成 $A=bQ+r$，整理得 $a=b(Q+a)+r$，餘數範圍不變。 若 $b\lt0$，先用正除數 $B=|b|$，再把商 $Q$ 換成 $-Q$。 所有符號情形都不需要負餘數。

再證明唯一性。設 $a=bq+r=bq'+r'$，兩個餘數都在規定範圍內。 於是 $b(q-q')=r'-r$，但 $|r'-r|\lt|b|$。$b$ 的非零整數倍 絕對值至少是 $|b|$，故 $r'=r$。再由 $b\ne0$ 得 $q'=q$。 嚴格上界保證唯一性；僅要求餘數非負並不足夠。

常見錯誤

不能忽略餘數範圍

只寫 $a=bq+r$ 並不足夠。若不限制 $r$，同一個 $a$ 可以有無限多種表示。條件 $0\le r\lt|b|$ 才會選出標準的商與餘數。

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

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

定理

最大公因數的一步不變性

若 $a=bq+r$，則

$$\gcd(a,b)=\gcd(b,r).$$

證明: 保留整個共同因數集合

目標是證明兩個最大公因數相等。先證明更強的中間命題，論證會更直接： 整數 $h$ 同時整除 $a,b$，當且僅當它同時整除 $b,r$。 正向用 $r=a-bq$，反向用 $a=bq+r$，兩者都用整數線性組合的整除性質。

輸入不同時為零時，兩個因數集合相同，所以最大元素相同。若 $a=b=0$， 則 $r=0$，兩邊按約定都是 $0$。這個恆等式本身不要求餘數範圍； 餘數範圍的作用是保證算法向前推進。

概念視角算法

不變量與遞減計算

每次替換 $(a,b)\mapsto(b,r)$，最大公因數保持不變，餘數則變小。 兩者各有作用：不變性保證最後答案就是原本的最大公因數，嚴格遞減則保證 計算會結束。先取輸入的絕對值，把較大的正數放在前面；若另一輸入是零， 立即停止。其餘每次帶餘除法都使用正除數。

例題

用歐幾里得算法求 $\gcd(7224,1290)$

反覆使用除法算法：

$$\begin{aligned} 7224&=1290\cdot5+774,\\ 1290&=774\cdot1+516,\\ 774&=516\cdot1+258,\\ 516&=258\cdot2+0. \end{aligned}$$

最後一個非零餘數是 $258$，所以

$$\gcd(7224,1290)=258.$$

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

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

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

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

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

例題

倒代回去

由前面的計算，

$$258=774-516.$$

代入 $516=1290-774$：

$$258=774-(1290-774)=2\cdot774-1290.$$

再代入 $774=7224-5\cdot1290$：

$$258=2(7224-5\cdot1290)-1290 =2\cdot7224-11\cdot1290.$$

因此

$$258=7224\cdot2+1290\cdot(-11).$$

倒代也可整理成向前更新的係數。對正輸入設 $r_0=a$、$r_1=b$， 保存 $r_k=s_ka+t_kb$，初始係數為 $(s_0,t_0)=(1,0)$、 $(s_1,t_1)=(0,1)$。若 $r_{k+2}=r_k-q_{k+1}r_{k+1}$，則

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

代入兩個已知線性組合即可證明更新式。係數始終是整數，最後非零餘數那一行 便給出最大公因數所需的係數。

從歐幾里得除法得到 Bézout 係數

向下的歐幾里得計算和向上的倒代不是兩個互不相干的技巧。它們是同一批帶餘除法等式的兩種讀法：先用來找最後非零餘數，再把那個餘數改寫成原本兩個整數的線性組合。

觀看歐幾里得算法如何先找出 gcd，再倒代成可用於整數方程的具體 Bézout 恆等式。

1. 第一次帶餘除法

   計算由 7224=1290*5+774 開始，所以下一對數是 (1290,774)。

2. gcd 不變量

   若 a=bq+r，則 (a,b) 的正共同因數正好就是 (b,r) 的正共同因數。

3. 餘數鏈

   餘數 774, 516, 258, 0 說明最後非零餘數是 gcd(7224,1290)=258。

4. 倒代

   把等式倒過來用，先得到 258=2*774-1290。

5. Bézout 組合

   代入 774=7224-5*1290，得到具體恆等式 258=2*7224-11*1290。

6. 方程判別

   一次整數方程 ax+by=c 有整數解，當且僅當 gcd(a,b) 整除 c。

歐幾里得算法向下經過越來越小的餘數來求 gcd。擴展算法再把同一批等式倒過來讀，把 gcd 寫成 Bézout 組合，因此 gcd(a,b) 會控制 ax+by=c 何時有整數解。

定理

Bézout 恆等式

對任意整數 $a,b$，存在整數 $x,y$ 使得

$$\gcd(a,b)=ax+by.$$

對帶符號的非零輸入，先用 $|a|,|b|$ 計算，再把原本符號吸收到係數中。 若一項為零，用 $|a|=a\operatorname{sgn}(a)$ 或 $b$ 的對應等式； 若兩項皆零，取 $x=y=0$。這樣便證明恆等式的全部情形。

輸入不同時為零時，最大公因數也是最小的正整數線性組合。恆等式保證它 確實是一個組合；其他正組合都是它的正倍數，不可能更小。若輸入是 $(0,0)$， 則沒有正組合。

定理

互質判別

設 $a,b$ 為非零整數。則 $a,b$ 互質，當且僅當存在整數 $x,y$ 使得

$$ax+by=1.$$

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

例題

擴展歐幾里得表格的結果

對 $12345$ 與 $11111$，歐幾里得算法給出

$$\begin{aligned} 12345&=11111\cdot1+1234,\\ 11111&=1234\cdot9+5,\\ 1234&=5\cdot246+4,\\ 5&=4\cdot1+1,\\ 4&=1\cdot4+0. \end{aligned}$$

所以最大公因數是 $1$。倒代或使用係數表格可得

$$1=12345(-2224)+11111(2471).$$

相繼的係數對為

$$(1,0),\ (0,1),\ (1,-1),\ (-9,10),\ (2215,-2461),\ (-2224,2471).$$

例如餘數 $4$ 的係數來自 $(1,-1)-246(-9,10)=(2215,-2461)$。 下一行再由 $(-9,10)$ 減去這一對，便得到上面的恆等式。

這特別證明 $12345$ 與 $11111$ 互質。

共同因數與 Euclid 引理

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

定理

共同因數整除最大公因數

對整數 $a,b,n$，

$$n\mid a\text{ and }n\mid b \quad\Longleftrightarrow\quad n\mid \gcd(a,b).$$

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

定理

Euclid 引理

設 $p$ 是質數。若 $p\mid ab$，則 $p\mid a$ 或 $p\mid b$。

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

$$am+pn=1.$$

兩邊乘以 $b$ 得

$$abm+pbn=b.$$

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

同一證明也給出不要求質數的消去規則：若 $\gcd(u,v)=1$ 且 $v\mid ut$， 則 $v\mid t$。把 Bézout 等式 $u\alpha+v\beta=1$ 乘以 $t$， 左邊兩項都被 $v$ 整除。這對帶符號整數也適用，下面整數方程的參數步驟 正需要這個結論。

例如，若 $a\mid c$、$b\mid c$ 且 $\gcd(a,b)=1$，則 $ab\mid c$。 由 $a\mid c$ 寫成 $c=at$，其中 $t$ 是整數。因為 $b\mid at$，互質消去 給出 $b\mid t$，所以 $t=bk$，從而 $c=abk$，其中 $k$ 是整數。 互質條件不可省略：$4\mid12$ 且 $6\mid12$，但 $24\nmid12$。

唯一質因數分解

定理

算術基本定理

每個大於 $1$ 的正整數都可以寫成質數乘積，而且這個乘積在不計因子次序下唯一。

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

唯一性使用 Euclid 引理。若

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

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

反覆使用 Euclid 引理，可以從整除有限乘積推到整除其中一個因子。 消去過程不能只耗盡一邊的質數：否則 $1$ 會等於非空質數乘積，而該乘積 大於 $1$。因此兩邊因子數相同，計入重數後的因子也相同。

對正整數 $a,b$，這個定理也給出比較指數的方法。若

$$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)}.$$

用同一記號，$a\mid b$ 當且僅當每個質數都滿足 $m_i\le n_i$。 正共同因數最多含有 $\min(m_i,n_i)$ 個相應質因子；取齊這些允許的因子， 所得共同因數便被其他每個共同因數整除。帶符號非零輸入先取絕對值， 零輸入則用最大公因數的約定處理。

例題

用質因數冪次求最大公因數

因為

$$144=2^4\cdot3^2,\qquad 60=2^2\cdot3\cdot5,$$

所以

$$\gcd(144,60)=2^2\cdot3^1\cdot5^0=12.$$

一次 Diophantine 方程

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

$$ax+by=c$$

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

定理

可解條件

設 $a,b,c\in\mathbb Z$，且 $d=\gcd(a,b)$。方程

$$ax+by=c$$

有整數解 $(x,y)$，當且僅當 $d\mid c$。

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

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

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

先設 $a,b$ 都非零。已知一組解後，可以描述所有解。設 $d=\gcd(a,b)>0$，並令

$$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.$$

這裏須證明兩件事。首先代入參數式，額外項 $a(kv)-b(ku)=0$ 相消， 所以每個列出的整數對都是解。再證明完整性：從任意另一組解減去 $(x_0,y_0)$ 的方程，得到

$$u(x-x_0)=-v(y-y_0).$$

由 $\gcd(u,v)=1$ 和消去規則，$v\mid(x-x_0)$，故可寫成 $x-x_0=kv$。代回後消去非零整數 $v$，得 $y-y_0=-ku$。 這才證明沒有其他解；試出幾個整數對不能證明完整性。

消去前須先處理零係數。若 $a=0$、$b\ne0$，當且僅當 $b\mid c$ 有解， 此時 $y=c/b$，$x$ 可為任意整數。若 $b=0$、$a\ne0$，則在 $a\mid c$ 時有 $x=c/a$，$y$ 任意。若 $a=b=0$，則 $c=0$ 時所有整數對都是解， $c\ne0$ 時無解。這與 $0\mid c$ 當且僅當 $c=0$ 一致，無須除以零的最大公因數。

例題

量水問題

若有 $180$ mL 的杯和 $105$ mL 的玻璃杯，能否量出剛好 $30$ mL？代數上，我們要判斷

$$180x+105y=30$$

是否有整數解。因為

$$\gcd(180,105)=15$$

且 $15\mid 30$，所以有解。

由擴展歐幾里得算法，

$$15=180\cdot3-105\cdot5.$$

乘以 $2$ 得

$$30=180\cdot6-105\cdot10.$$

所以一組解是 $(x,y)=(6,-10)$。因為 $a/d=12$ 且 $b/d=7$，所有解為

$$(x,y)=(6+7k,-10-12k),\qquad k\in\mathbb Z.$$

在量水解釋中，正係數表示往桶中加入，負係數表示移走。先倒入六杯 $180$ mL，再移走十玻璃杯 $105$ mL，桶內剩下 $1080-1050=30$ mL。 整數解並不要求兩個係數都非負。

快速檢查

思考檢查

以整數語言來說，$a\mid b$ 是甚麼意思？

留意定義中隱含的存在量詞。

解答 · 答案

它表示存在整數 $d$ 使得 $b=ad$。

思考檢查

為甚麼 $a$ 和 $b$ 的每個共同因數都會整除 $ax+by$，其中 $x,y\in\mathbb Z$？

分別使用兩次整除定義。

解答 · 答案

若 $n\mid a$ 且 $n\mid b$，則 $a=nr$、$b=ns$，其中 $r,s$ 是整數。因此 $ax+by=n(rx+sy)$，而 $rx+sy$ 仍是整數。

思考檢查

在 $7224$ 與 $1290$ 的歐幾里得算法中，為甚麼最大公因數是最後一個非零餘數？

每一步都用 $\gcd(a,b)=\gcd(b,r)$。

解答 · 答案

每次除法都保留最大公因數，所以原本的最大公因數等於最後一個非零餘數 $258$ 與 $0$ 的最大公因數，即 $258$。

思考檢查

判斷 $ax+by=c$ 是否有整數解的條件是甚麼？

用 $\gcd(a,b)$ 表述。

解答 · 答案

方程有整數解，當且僅當 $\gcd(a,b)\mid c$。

練習

1. 列出 $84$ 的所有正因數，並求 $\gcd(84,60)$。
2. 用除法算法把 $-37$ 寫成 $-37=5q+r$，其中 $0\le r\lt5$。
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)$。

解答 · 參考解答 1

$84$ 的正因數是 $1,2,3,4,6,7,12,14,21,28,42,84$。又 $60=2^2\cdot3\cdot5$，$84=2^2\cdot3\cdot7$，所以 $\gcd(84,60)=12$。

解答 · 參考解答 2

餘數要介乎 $0$ 和 $4$ 之間。因為 $-37=5(-8)+3$，所以 $q=-8$，$r=3$。

解答 · 參考解答 3

$252=198\cdot1+54$，$198=54\cdot3+36$， $54=36\cdot1+18$，$36=18\cdot2+0$。因此 $\gcd(252,198)=18$。

解答 · 參考解答 4

倒代： $18=54-36=54-(198-3\cdot54)=4\cdot54-198$。 又 $54=252-198$，所以 $18=4(252-198)-198=4\cdot252-5\cdot198$。

解答 · 參考解答 5

由 Bézout 恆等式，$\gcd(a,b)=ax+by$。若 $n$ 同時整除 $a,b$， 則 $n$ 整除右邊，因此整除 $\gcd(a,b)$。

解答 · 參考解答 6

$\gcd(35,21)=7$，且 $7\mid14$，所以有解。直接驗證 $35(1)+21(-1)=14$，所以 $(x,y)=(1,-1)$ 是一組解。全部解為 $(1+3k,-1-5k)$，其中 $k$ 為整數，因為 $35/7=5$、$21/7=3$。

解答 · 參考解答 7

$\gcd(35,21)=7$，但 $7\nmid10$，所以沒有整數解。

解答 · 參考解答 8

比較每個質數的較小指數： $2^{\min(4,3)}3^{\min(2,5)}5^{\min(1,0)}7^{\min(0,1)} =2^3\cdot3^2=72$。