不定方程

我们用 $x$ 表示 3 个装的包数，用 $y$ 表示 5 个装的包数。字母只是给还没确定的数起一个名字。如果 $x = 3$，第一种包一共提供 $3 + 3 + 3 = 3 \times 3 = 9$ 个物品；如果 $y = 4$，第二种提供 $5 + 5 + 5 + 5 = 5 \times 4 = 20$ 个。加起来就是 $9 + 20 = 29$。

符号 $\in$ 的意思是“属于”。花括号列出允许使用的数，省略号表示还可以继续。这里 $x$、$y$ 可以是 0，因为某一种包可以一包也不拿；不能是负数，因为包数不能为负；也不能是分数。0、1、2、…… 这些数叫作非负整数。

下面两个滑块改变的是两种包的包数。绿色框中有 3 个点，黄色框中有 5 个点，每个点就是一个物品。目标 29 保持不变，我们可以观察 $3x$ 和 $5y$ 怎样合成总数。再试一试 $x = 8$、$y = 1$：$3 \times 8 + 5 \times 1 = 24 + 5 = 29$，这又是一个办法。

现在把方程和整包这个故事分开。整数也可以是负数：……、$-3$、$-2$、$-1$、0、1、2、3、……。我们用 $\mathbb Z$ 表示所有整数。例如 $x = -2$、$y = 7$ 也满足 $3 \times (-2) + 5 \times 7 = -6 + 35 = 29$。它是这个方程的整数解，却不是一个能实际拿包的方案。所以解题时一定要说清：我们找的是所有整数解，还是只找非负整数解。

要求未知数只能取整数的方程，叫作不定方程。接下来的二元一次例子会出现没有整数解或有无穷多个整数解的情况，而后面的非线性例子恰好只有六个整数解。关键在于未知数的取值被限制为整数。

不用同时猜两个数：选定 $x$ 后，凑到 29 的要求就决定了 $y$ 应该是多少。在等式两边减去 $3x$，左边会留下 $5y$。把这个等式的两边除以不为零的 5，就能得到 $y$。

$x = 0$ 时，$y = (29 - 3 \times 0)/5 = 29/5 = 5.8$。它确实满足等式：$3 \times 0 + 5 \times 5.8 = 29$，可是 5.8 不是整数。$x = 3$ 时，$y = (29 - 9)/5 = 20/5 = 4$，这次是整数。如果允许未知数取实数，两组都可以；如果要求取整数，只有后一组可以。这里实数包括整数、分数，也包括数轴上的其他数。

为了把区别画出来，我们让两条数轴在零的位置相交。横着的轴记录 $x$，竖着的轴记录 $y$。(3, 4) 的意思是：从交点向右走 3 格，再向上走 4 格。在两个坐标都是整数的位置，我们放一个灰点。这样整齐排开的点叫作整数格点。我们要找的是算出的点恰好落在灰点上的情况，而不是落在灰点之间。

为什么紫色图像是一条直线？让 $x$ 增加 $h$，代入 $x + h$，得到 $y = (29 - 3x - 3h)/5 = (29 - 3x)/5 - 3h/5$。也就是说，横着变化 $h$，竖着总会变化 $-3h/5$，当 $h \ne 0$ 时，把竖直变化 $-3h/5$ 除以水平变化 $h$，得到 $-3/5$，两种变化的比例固定。这就是斜率为 $-3/5$ 的直线；斜率记录的是竖直变化除以水平变化。直线上也包含分数坐标，只有其中两个坐标都为整数的点，才回答了整数解的问题。

如果只找非负包数，$x$ 不可能超过 9：一旦 $x \ge 10$，第一种包就至少提供 $3 \times 10 = 30$ 个，已经超过 29。所以对这道具体的整包题，检查 $x = 0$ 到 9 确实覆盖了全部非负可能。但它还没有覆盖全部整数解，因为 $x$ 可以为负，$y$ 也就可以更大。要处理全部整数，我们需要一个不受这幅有限图像限制的证明。

把每包大小改成 6 和 9，再把目标改成 31。我们先不试很多组数，而是观察：6 和 9 都是 3 的倍数。不管取多少包，每一种提供的总数仍是 3 的倍数，两种加起来也改变不了这一点。

只要 $x$、$y$ 是整数，$2x + 3y$ 就是整数，因此左边恰好是 3 乘以一个整数。31 却不是，31 除以 3 商 10、余 1。所以 $6x + 9y = 31$ 没有整数解，即使允许 $x$、$y$ 为负也不行。这和“试了很多次没找到”不同：我们已经证明它不可能存在。

现在把同样的想法写成一般形式。暂时设 $a$、$b$ 是正整数，目标 $c$ 是整数。如果存在整数 $A$，使 $a = dA$，我们就说正整数 $d$ 整除 $a$，记作 $d \mid a$。能够同时整除 $a$ 和 $b$ 的数叫作公因数，其中最大的正数叫作最大公因数，记作 $\gcd (a, b)$。这里它一定存在：1 是公因数，而 $a$ 的正因数不会超过正数 $a$，所以可选的数是一个非空的有限集合。

假如 $ax + by = c$ 有整数解，最后一行就说明 $c$ 等于 $d$ 乘以整数 $Ax + By$，因此必须有 $d \mid c$。我们把这样的条件叫作必要条件：缺少它，解一定不存在。但目前还不能说满足它就一定有解。反过来的方向，还需要另外证明。

我们现在的目标，是把最大公因数写成“$a$ 乘一个整数，再加上 $b$ 乘一个整数”。为什么要这样写？因为只要 $d$ 整除 $c$，我们就能把这两个整数同时乘以 $c/d$，让右边从 $d$ 变成 $c$。带余除法正好能帮我们做出这种表示。

先用 3 和 5 完整做一遍

从 5 里拿走一组 3，剩下 2；再从 3 里拿走一组 2，剩下 1；最后 2 恰好包含两组 1，不剩东西。每一步新的余数，都小于刚才用来除的那个数。

最后一个非零余数是 1。为了把它写成最初的 3 和 5 的组合，我们倒着读第二个等式：$1 = 3 - 2$。而第一个等式说明 $2 = 5 - 3$。把这里的 2 换掉，再把括号前的负号分别乘进去。

所以 $(58, -29)$ 是 $3x + 5y = 29$ 的一个整数解。直接检查：$3 \times 58 = 174$，$5 \times (-29) = -145$，而 $174 - 145 = 29$。它不是一个实际的拿包方案，不过我们当前的目标只是找到一个整数解，这一步已经完成。稍后我们会从一个解走到其他全部解，其中就包含 (3, 4)。

为什么这样的相除一定会停下来？

对两个正整数 $U$、$V$，我们从 $U$ 中不断拿走整组 $V$，直到剩下的数小于 $V$。如果一开始 $U < V$，那就一组也不拿。每次至少减少 1，又不能剩下负数，所以一定只需要有限次。用 $q$ 记录拿走的组数，用 $r$ 记录余数，就得到 $U = qV + r$，其中 $q$ 是非负整数，$0 \le r < V$。

如果 $r$ 不为零，就对新的一对数 $(V, r)$ 重复这件事。每次第二个数都会变成更小的正整数。正整数不可能这样无限下降：从 $V$ 开始，最多经过 $V - 1$、$V - 2$、……、1 中的有限个数。因此最终一定出现余数 0。这种反复做带余除法的方法，叫作辗转相除法。

为什么最后保留下来的非零数是最大公因数？

这一步不能只靠观察。我们要证明，把 $(U, V)$ 换成 $(V, r)$ 时，公因数一个也没变。假如 $k$ 同时整除 $U$、$V$，就能写 $U = km$、$V = kn$。于是 $r = U - qV = km - qkn = k(m - qn)$，说明 $k$ 也整除 $r$。所以 $U$、$V$ 的每一个公因数，也都是 $V$、$r$ 的公因数。

反过来，假如 $k$ 同时整除 $V$、$r$，就写 $V = kn$、$r = ks$。这样 $U = qV + r = qkn + ks = k(qn + s)$，所以 $k$ 也整除 $U$。两个方向都证明了：替换前后的公因数完全相同。最后得到的一对数是 $(d, 0)$。$d$ 的每个正因数也整除 0，因为 $0 = k \times 0$；其中最大的就是 $d$ 自己。既然每次替换都没有改变公因数，这个 $d$ 也就是最初 $a$、$b$ 的最大公因数。

为什么 $d$ 一定能写成 $a$、$b$ 的整数倍之和？

最开始，$a = 1a + 0b$、$b = 0a + 1b$，已经都是我们要的形式。假设某一步的两个数能写成 $U = ma + nb$、$V = pa + sb$，其中系数都是整数。下一步的余数就是 $U - qV$。把它展开，就能看清新系数是什么。

$m - qp$、$n - qs$ 仍是整数，因为整数相加、相减、相乘后还是整数。所以每往前一步，这种形式都被保留下来。最后留下的 $d$ 是过程中保留过的一个数。如果第一次相除就整除，$d$ 可能直接是原来的数；否则它是后面出现的余数。两种情况都保持这个形式，因此一定存在整数 $u$、$v$，使 $au + bv = d$。像前面那样倒着把余数替换回去，就能算出 $u$、$v$。这条结论常叫作贝祖等式；名字只是为了方便引用，并没有代替刚才的证明。

如果 $d$ 整除 $c$，那么 $k = c/d$ 是整数，最后一行就真的构造出整数解 $x = ku$、$y = kv$。于是两个方向都完整了：对正整数 $a$、$b$，$ax + by = c$ 有整数解，当且仅当 $\gcd(a, b)$ 整除 $c$。“当且仅当”就是两边可以互相推出的意思。请注意，这里保证的是整数解，还没有保证非负。

对 $6x + 9y = 30$，带余除法给出 $9 = 1 \times 6 + 3$、$6 = 2 \times 3 + 0$。倒过来就是 $3 = 9 - 6$。因为 $30/3 = 10$，两边乘以 10，得到 $30 = 10 \times 9 - 10 \times 6 = 6 \times (-10) + 9 \times 10$。所以 $(-10, 10)$ 是一个解。而 3 不管乘哪个整数，都得不到 31，这也和前面的必要条件证明吻合。

回到 $3x + 5y = 29$，从解 (3, 4) 开始。让 $x$ 增加 5，就给总数增加 $3 \times 5 = 15$；同时让 $y$ 减少 3，又从总数拿走 $5 \times 3 = 15$。两个变化抵消，所以 (8, 1) 还是解。反方向走一步则得到 $(-2, 7)$。重复整数次这样的移动，我们就想到 $x = 3 + 5t$、$y = 4 - 3t$，其中 $t$ 可以是任意整数，也可以为负或为零。

代入证明了：我们用这个规则造出来的每一对数都正确。但会不会有另一个解，这个规则永远走不到？为了回答它，我们从任意一个整数解 $(x, y)$ 出发，也就是不预先假定它属于刚才的列表。把它满足的等式 $3x + 5y = 29$，减去已知等式 $3 \times 3 + 5 \times 4 = 29$。

符号 $\Delta$ 在这里表示变化：$\Delta x$ 就是 $x - 3$，不是在做一种新的乘法。我们需要证明 $\Delta x$ 是 5 的倍数。这一步不能凭感觉把整除关系里的 3 划掉。我们可以使用前面已经算出的 $2 \times 3 - 5 = 1$。把两边乘以 $\Delta x$，然后把 $3\Delta x$ 换成 $-5\Delta y$。

括号里是整数，所以存在整数 $t$，使 $\Delta x = 5t$。把它代入 $3\Delta x = -5\Delta y$，得到 $15t = -5\Delta y$；再除以不为零的 $-5$，得到 $\Delta y = -3t$。因此，刚才任意拿来的解都必须写成 $x = 3 + 5t$、$y = 4 - 3t$。两个方向都证明了：造出来的全是解，所有整数解也全能造出来。这才叫完整的解答。

把同一段推理写成一般形式

现在设 $a$、$b > 0$，$d = \gcd (a, b)$，并且 $d$ 整除 $c$。设 $(x_{0}, y_{0})$ 是已经找到的一个整数解；右下角的 0 只是给起点做标记。记 $A = a/d$、$B = b/d$，它们都是正整数。$A$、$B$ 不可能有大于 1 的公因数 $h$：否则 $dh$ 就会同时整除 $a$、$b$，而 $h > 1$ 又使 $dh > d$，这和 $d$ 是最大公因数矛盾。因此 $A$、$B$ 的最大公因数是 1，我们说它们互质。

最后一行是把前一行除以 $d$ 得到的，因为 $d > 0$，这个除法合法。$A$、$B$ 互质，所以前面完整证明过的辗转相除论证保证，存在整数 $u$、$v$，使 $uA + vB = 1$。两边乘以 $\Delta x$，再把 $A\Delta x$ 换成 $-B\Delta y$，右边的两项就都会带上 $B$。

因此存在整数 $t$，使 $\Delta x = Bt$。再代入 $A\Delta x = -B\Delta y$，得到 $ABt = -B\Delta y$。因为 $B > 0$，可以除以 $B$，得到 $\Delta y = -At$。反过来，这样的变化总会抵消：$a(Bt) + b(-At) = (ab/d)t - (ba/d)t = 0$。我们再次完成了两个方向，因此全部整数解恰好是下面这些。

这也解释了为什么我们可以换一个方便的起点。从整包方程通过辗转相除得到的 $(58, -29)$ 出发，取 $t = -11$，就有 $x = 58 + 5 \times (-11) = 3$、$y = -29 - 3 \times (-11) = 4$。改从 (3, 4) 开始，只是给同一批解换了参数编号。对 $6x + 9y = 30$，$d = 3$，每步的移动是 $(9/3, -6/3) = (3, -2)$。从 $(-10, 10)$ 走四步，得到 $(-10 + 12, 10 - 8) = (2, 2)$。

下面模型的横坐标仍是 $x$，纵坐标仍是 $y$。绿点都是整数解，黄色圆圈标出当前选择。选定方程后，让 $t$ 改变一个整数步。直角虚线的横向一段表示 $x$ 的变化，竖向一段表示 $y$ 的变化，旁边的算式检查总数仍然固定。也可以试一下目标 31：那里没有整数解，是因为算术上的矛盾，不是因为点藏在画面外面。

$3x + 5y = 29$ 的全部整数解已经是 $x = 3 + 5t$、$y = 4 - 3t$。现在回到整包题，还要同时满足 $x \ge 0$、$y \ge 0$。所以我们把两个不等式都放到同一个参数 $t$ 上，而不是分别选择两个互不相关的数。

第一行两边减去 3，得到 $5t\ge-3$；两边除以正数 5，不等号方向不变。第二行两边加上 $3t$，得到 $4\ge3t$；两边除以正数 3，同样不改变不等号方向。合起来就是 $-3/5 \le t \le 4/3$。因为 $-1 < -3/5 < 0$，而 $1 < 4/3 < 2$，这个区间中只有两个整数：0 和 1。

所以整包方案恰好只有 (3, 4) 和 (8, 1)。这个“恰好”现在有两个依据：前面检查过全部非负 $x$，刚才又从已经证明完整的整数通解中筛选。写竞赛解答时，要让读者看到这个没有遗漏的理由，而不是只列出两个碰巧算对的方案就结束。

为了反复使用，我们把“不小于 $r$ 的最小整数”记作 $\lceil r\rceil$，把“不大于 $r$ 的最大整数”记作 $\lfloor r\rfloor$。这是向上取整和向下取整的定义。比如 $\lceil -3/5\rceil = 0$，因为 0 是它右边遇到的第一个整数；$\lfloor 4/3\rfloor = 1$，因为 1 是它左边最后一个整数。记 $A = a/d > 0$、$B = b/d > 0$，两个非负条件就可以写成下面这样。

如果下面的整数界限反而大于上面的界限，那就没有非负解，即使整数解存在。例如 $3x + 5y = 1$ 有整数解 $(2, -1)$，因为 $6 - 5 = 1$；全部解是 $x = 2 + 5t$、$y = -1 - 3t$。非负要求 $t \ge -2/5$，也就是整数 $t \ge 0$，同时 $t \le -1/3$，也就是整数 $t \le -1$。两者无法同时满足。这就是为什么 $\gcd(a, b)$ | $c$ 本身还不能直接解决实际计数问题。

到现在为止，每个未知数都只是乘以固定的系数，这样的方程是一次的。现在考虑 $xy = x + y + 3$，仍要求 $x$、$y$ 是整数。这里出现了两个未知数的乘积 $xy$，方程的结构变了，前面的二元一次通解公式不能直接使用。我们要找一个办法，把它变成可以列完的整数问题。

既然有乘积，我们就试着把它写成两个因数。先把两边都减去 $x$、$y$，得到 $xy - x - y = 3$。左边看起来接近 $(x - 1)(y - 1)$，但我们先展开检查：$(x - 1)(y - 1) = xy - x - y + 1$。差的正好是 $+1$，所以在原等式两边都加上 1。

记 $u = x - 1$、$v = y - 1$，方程就成了 $uv = 4$。整数减去 1 还是整数；反过来，每个整数 $u$ 也都给出整数 $x = u + 1$。所以这个替换不会丢掉整数对，也不会凭空增加整数对。接下来要列出 4 的全部有序因数对。“有序”是说第一个数负责 $x$，第二个负责 $y$，交换位置可能得到不同的解。

两个因数都不能为零，因为乘积是 4。它们必须同号，因为一正一负相乘会得到负数。如果都为正，每一个至少是 1，所以任何一个都不能超过 4。检查 $u = 1$、2、3、4，对应的 $v = 4/u$ 分别为 4、2、$4/3$、1，其中第三个不是整数。如果都为负，就写 $u = -s$、$v = -r$，其中 $s$、$r$ 为正。此时 $uv = sr = 4$，所以全部负因数对，就是刚才三个正因数对同时变号。

在下面选一对因数，模型会给两个坐标分别加 1，再单独算原方程的左边和右边。由于每一步变形都能倒过来做，而且因数对已经列全，这六对就是全部整数解。如果题目要求的是正整数 $x$、$y$，我们就只保留 (2, 5)、(3, 3)、(5, 2)，其余三对含有零或负数。

下面矩形里，每个小方块边长为 1、面积为 1。横向标记 $|u|$、纵向标记 $|v|$ 表示绝对值，也就是去掉负号后数的大小。例如 $|-2| = 2$，$|2| = 2$。两个边长相乘，数出的就是四个小方块。对负因数对，矩形只表示大小，两个负号仍要在算式中另外检查。

不是每个方程都能变成方便的乘积。来看 $x^{2} + y^{2} = 3$，要求 $x$、$y$ 是整数，这里的 $x^{2}$ 就是 $x \times x$。我们可以试几个绝对值小的整数，但“没试出来”不是无解的理由。我们将证明：左边和右边除以 4 的余数根本对不上。这也和同余有关：两个整数模 4 同余，就是说它们的差能被 4 整除，也就是除以 4 时余数相同。

这两种说法为什么一样？把两个整数写成 $4q + r$、$4s + u$，其中 $r$、$u$ 都是 0、1、2、3 之一。两数的差就是 $4(q - s) + (r - u)$。余数相同时，它能被 4 整除；反过来，如果差能被 4 整除，那么 $r - u$ 也必须是 4 的倍数。但 $-3 \le r - u \le 3$，这之间唯一的 4 的倍数是 0，所以 $r = u$。

每个整数 $n$，包括负整数，都落在某一段从 $4q$ 到 $4q + 3$ 的整数里，因此 $n = 4q + r$，其中 $r$ 是 0、1、2、3 之一。要严格选出 $q$，可以取 $q = \lfloor n/4\rfloor$，于是 $q \le n/4 < q + 1$；两边乘以 4，再减去 $4q$，得到 $0 \le n - 4q < 4$。例如 $-1 = 4 \times (-1) + 3$。现在把四种形式分别平方，检查哪些部分是 4 的倍数。

这里每次展开都用了 $(a + b)^{2} = a^{2} + ab + ba + b^{2} = a^{2} + 2ab + b^{2}$，它就是把两个括号逐项相乘的结果。右边每个括号里都是整数，所以任何整数平方除以 4，只会余 0 或余 1。两个平方相加，余数的和只有 $0 + 0 = 0$、$0 + 1 = 1$、$1 + 0 = 1$、$1 + 1 = 2$，都还不到 4，不需要再减去 4，也没有一个是 3。

$x^{2} + y^{2} = 3$ 的右边除以 4 余 3。如果等式两边是同一个整数，余数也必须相同。现在余数不可能相同，所以它没有整数解。同一段计算也排除了所有除以 4 余 3 的目标。但反过来的结论并没有证明：通过这个余数检查，只是没有被这项必要条件排除。就像前面证明一次方程的可解条件时那样，两个方向不能混为一谈。

每道题先想一想：完整的答案需要什么？是证明不可能，是找到一个解再说明全部移动，还是列全因数对？下面的解答可以自己展开，不会自动出现。我们对照的不只是最终数值，还有为什么没有遗漏。

如果系数是零，或者是负数呢？

主证明明确要求 $a$、$b > 0$，是为了保证除法和非负不等式中的方向清楚。不能把零硬塞进那个证明的分母。如果 $a = 0$、$b \ne 0$，方程就是 $by = c$；只有 $c/b$ 是整数时才有解，此时 $y = c/b$，而 $x$ 可以是任意整数。如果 $b = 0$、$a \ne 0$，就要求 $x = c/a$ 是整数，而 $y$ 任意。如果两个系数都是零，左边总是零：$c = 0$ 时每一对整数都满足，$c \ne 0$ 时一对也不满足。

非零负系数可以通过改变对应未知数的符号来处理。例如定义 $X = -x$，$-3x + 5y = 29$ 就变成 $3X + 5y = 29$。每个整数 $x$ 都恰好对应一个整数 $X$，反过来 $x = -X$，所以整数解不会改变。我们已知 $X = 3 + 5t$、$y = 4 - 3t$，于是 $x = -3 - 5t$。检查：$-3(-3 - 5t) + 5(4 - 3t) = 9 + 15t + 20 - 15t = 29$。如果还有非负限制，也要一同翻译：$x \ge 0$ 对应的是 $X \le 0$，而不是 $X \ge 0$。

现在我们可以把前面做过的事情和线性代数接起来，而不必突然引入一种没解释的方法。在线性代数里，一对数可以竖着写成一列，这里我们把这样的列叫作向量。两列相加，就是第一个数和第一个数相加，第二个数和第二个数相加；一列乘以某个数，就是每个位置都乘以它。这些操作描述的，正是我们刚才使用的坐标移动。

对 $6x + 9y = 30$，我们从 (2, 2) 开始。列 $(3, -2)$ 表示一种移动：第一个坐标加 3，第二个坐标减 2。方程检查一对数的方法，是把第一个数乘以 6，第二个数乘以 9，再相加。我们可以用一行 [6 9] 记录这个操作，叫作只有一行的矩阵。这里的矩阵乘法就是下面这个定义。

把加法写进矩阵符号之前，我们先展开里面的普通算术。列 $p$ 的两个数记作 $p_{1}$、$p_{2}$，另一列 $z$ 的两个数记作 $z_{1}$、$z_{2}$。右下角的 1、2 表示第一个、第二个位置，不是幂。两列相加后，两个位置分别是 $p_{1} + z_{1}$、$p_{2} + z_{2}$。现在第一个乘以 6，第二个乘以 9。

减法也一样展开：$6(w_{1} - p_{1}) + 9(w_{2} - p_{2}) = 6w_{1} - 6p_{1} + 9w_{2} - 9p_{2} = (6w_{1} + 9w_{2}) - (6p_{1} + 9p_{2})$，简写为 $M(w - p) = Mw - Mp$。因此下面简短的矩阵规则，来自刚才逐项使用的分配律，不是突然增加的假设。

这个移动给总数带来的变化是零，所以它可以加到原来的解上。更一般地，如果列 $p$ 满足 $Mp = c$，而列 $z$ 满足 $Mz = 0$，利用普通乘法的分配律，就有 $M(p + z) = Mp + Mz = c + 0 = c$。反过来，如果另一列 $w$ 也满足 $Mw = c$，两式相减得到 $M(w - p) = Mw - Mp = c - c = 0$。于是每一个解，都可以写成“一个特定解，加上一个使输出为零的移动”。