一次不定方程：先找一组，再走通解

方程 $ax+by=c$（$a,b$ 不全为零）有整数解，当且仅当

必要性好证：$a,b$ 都是 $d=gcd(a,b)$ 的倍数，所以 $ax+by$ 也是 $d$ 的倍数，$c$ 必须是。

充分性来自贝祖定理：存在 $x_0,y_0$ 使 $a{x}_0+b{y}_0=d$，两边乘 $\frac{c}{d}$ 就得到一组解。

若 $(x_0,y_0)$ 是一组特解，$d=gcd(a,b)$，则全部整数解是

为什么加 $\frac{b}{d}$ 而不是 $b$：为了保证“所有”解都取到，步长必须是最小的正整数周期。

小系数直接观察：$3x+5y=1$，试 $x=2,y=-1$ 得 $6-5=1$，成了。

稍大的用辗转相除倒推：$17x+13y=1$。

$$17=13\times 1+4,13=4\times 3+1$$ 倒推：$1=13-4\times 3=13-(17-13)\times 3=13\times 4-17\times 3$。所以 $x=-3,y=4$。

再不行就试同余：$7x+11y=100$，模 $7$ 得 $4y\equiv 2\left(\mathrm{mod}7\right)$，$y\equiv 4\left(\mathrm{mod}7\right)$，取 $y=4$ 代回得 $x=8$。

例1 判断有解

判断 $6x+10y=7$ 是否有整数解。

解：$gcd(6,10)=2$，$2\nmid 7$，无整数解。

左边永远是偶数，右边是奇数，从奇偶也能看出矛盾。

例2 求通解

求 $3x+5y=1$ 的所有整数解。

解：特解 $(2,-1)$。$d=1$，通解 $$\{\begin{array}{c}x=2+5ty=-1-3t\hfill \end{array}(t\in \mathbb{Z})$$

验算 $t=1$：$x=7,y=-4$，$21-20=1$ ✓。

例3 正整数解

求 $3x+5y=30$ 的所有正整数解。

解：特解：试 $x=5,y=3$，$15+15=30$ ✓。

通解 $x=5+5t$，$y=3-3t$。

要 $x>0,y>0$：$5+5t>0$ ⇒ $t>-1$；$3-3t>0$ ⇒ $t<1$。所以 $t=0$。

唯一正整数解是 $(5,3)$。

例4 应用：买笔

用 $100$ 元买单价 $7$ 元和 $11$ 元的两种笔，钱刚好花完，问各买几支（都要买）。

解：$7x+11y=100$，$x,y$ 为正整数。

模 $7$：$4y\equiv 2\left(\mathrm{mod}7\right)$ ⇒ $y\equiv 4\left(\mathrm{mod}7\right)$。$y=4$ 或 $11$（$y<10$ 时 $11$ 太大，$11\times 11=121>100$）。

$y=4$：$7x=56$，$x=8$ ✓。

所以 $7$ 元的 $8$ 支，$11$ 元的 $4$ 支。

例5 方程的整数解个数

求 $5x+7y=100$ 的非负整数解个数。

解：模 $5$：$2y\equiv 0\left(\mathrm{mod}5\right)$ ⇒ $y\equiv 0\left(\mathrm{mod}5\right)$。

$y=0,5,10,15$（$y\le 14$）： $y=0$：$x=20$；$y=5$：$x=13$；$y=10$：$x=6$；$y=15$：$5x=-5$，不行。

共 $3$ 组非负解：$(20,0),(13,5),(6,10)$。