一次不定方程（组）

这一招在做什么

方程 $a x + b y = c$ 只有一个等式、却有两个未知数，所以叫不定方程。我们只要它的整数解——也就是直线上的整点。

a x + b y = c 有整数解 ⟺ d ∣ c, d = (a, b)

有解时，设 $(x_{0}, y_{0})$ 是一组解，全部解是

x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t (t 取遍所有整数)

先猜后证

$6 x + 9 y = 20$ 有多少组整数解？

一组也没有恰好一组有限的若干组无穷多组

先选定答案，才能看到结论。

第 1 / 5 步

系数大了，就让辗转相除替你找。先解 $a x + b y = d$ ，再整体放大 $c / d$ 倍。

切到底，“倒着写”那一列的最后一行给出

37 \times 6 + 13 \times (- 17) = 1

。所以

37 x + 13 y = 5

的一组特解是

(30, - 85)

。

三个未知数、两个方程，先消去一个，就回到上面的情形。

例（“百鸡问题”，出自《张丘建算经》） 公鸡每只 $5$ 钱，母鸡每只 $3$ 钱，小鸡 $3$ 只 $1$ 钱。用 $100$ 钱买 $100$ 只鸡，各买几只？

设公鸡 $x$ 只、母鸡 $y$ 只、小鸡 $z$ 只： $x + y + z = 100$ ， $5 x + 3 y + \frac{z}{3} = 100$ 。第二式乘 $3$ 再减去第一式，消去 $z$ ：

14 x + 8 y = 200 ⟺ 7 x + 4 y = 100.

特解 $(0, 25)$ ，通解 $x = 4 t$ ， $y = 25 - 7 t$ ，于是 $z = 75 + 3 t$ 。要三个数都不是负数， $t = 0, 1, 2, 3$ ：

(x, y, z) = (0, 25, 75), (4, 18, 78), (8, 11, 81), (12, 4, 84) .

Break it

结论： $a x + b y = c$ 有整数解

$6 x + 9 y = 21$ ： $(6, 9) = 3$ ， $3 ∣ 21$ 。直线上每隔 $(3, - 2)$ 就有一个整点。

练习 1基础

$5 x + 3 y = 31$ 有几组正整数解？

练习 2基础

$15 x + 21 y = c$ 有整数解，并且 $100 \leq c \leq 105$ 。 $c$ 可以是哪些数？

练习 3提高

把 $100$ 写成“ $7$ 的正整数倍”与“ $11$ 的正整数倍”之和： $100 = 7 x + 11 y$ ， $x$ 、 $y$ 是正整数。求 $x + y$ 。

练习 4挑战

只有 $5$ 分和 $8$ 分两种邮票（每种都足够多）。凑不出来的最大邮资是多少分？