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 恒等式

同一个计算可以倒推，将最大公因数写成原本两个数的整数线性组合。

观看欧几里得算法如何变成 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)$。