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