挑战≈ 16 分钟未开始

一次不定方程

核心概念

一次不定方程:形如

ax + by = c \qquad (a,b,c \text{ 为整数},\ a,b \text{ 不全为 } 0)

的方程,要求 $x,y$ 取整数解。因未知数多于方程,通常有无穷多组解,故称"不定"。

有解判别: $ax + by = c$ 有整数解的充要条件是 $\gcd(a,b) \mid c$ 。

通解结构:设 $d = \gcd(a,b)$ ,若 $(x_0, y_0)$ 是一组特解,则全部整数解为

x = x_0 + \frac{b}{d}\,t,\qquad y = y_0 - \frac{a}{d}\,t,\qquad t \in \mathbb{Z}.

为什么 $\gcd(a,b)\mid c$ 是有解的关键?因为 $ax+by$ 无论 $x,y$ 取什么整数,结果永远是 $\gcd(a,b)$ 的倍数(线性组合性质)。所以右边的 $c$ 也必须是 $\gcd$ 的倍数,否则无解。

找到一组解后,其余解都是"沿着方向 $(b/d,\ -a/d)$ 平移"得到的——加上这个向量, $ax+by$ 的值恰好不变。这就像在一条直线上,所有整点等间隔排开。实际应用("买若干元的甲乙两种物品恰好花光 $c$ 元")往往还要加上 $x,y\ge 0$ 的限制,从无穷多解中筛出有限组。

不定方程

gcd(3, 5) = 1，而 1 整除 22： 有整数解

(4, 2)

c22

先看 gcd(a,b) 是否整除 c——这是有解的充要条件。再在 x ≥ 0 中筛出让 y 也为非负整数的解。

例题 1判别并求通解

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

▸查看解答步骤

答: x=2+3t, y=-1-5t

例题 2带正整数限制的实际问题

某商品甲每个 $3$ 元、乙每个 $5$ 元,正好花 $22$ 元,问有几种购买方案(各至少买一个)?

所以唯一方案是甲买 $4$ 个、乙买 $2$ 个。

▸查看解答步骤

答: 只有 1 种:甲 4 个、乙 2 个

方程 $6x + 9y = 20$ 有整数解。

$\gcd(6,9)=3$ ,而 $3\nmid 20$ ,所以无整数解。

方程 $4x + 6y = 10$ 有整数解。

$\gcd(4,6)=2$ , $2\mid 10$ ,有解,例如 $x=1,y=1$ 。

$2x + 3y = 12$ 中,满足 $x\ge0,\ y\ge0$ 的整数解有几组?

$x$ 须使 $12-2x$ 被 $3$ 整除且非负: $x=0(y=4),\ x=3(y=2),\ x=6(y=0)$ ,共 $3$ 组。

$ax+by=c$ 有整数解的充要条件是?

\gcd(a,b)\mid c

a\mid c

且

b\mid c

c\mid \gcd(a,b)

a,b

互质

充要条件是 $\gcd(a,b)\mid c$ 。

方程 $5x + 3y = 7$ 有整数解。

$\gcd(5,3)=1$ , $1\mid7$ ,有解(如 $x=2,y=-1$ )。

$2x + 5y = 12$ 中满足 $x\ge0,\ y\ge0$ 的整数解有几组?

$y=0\Rightarrow x=6$ ; $y=2\Rightarrow x=1$ ; $y=1$ 时 $x=3.5$ 不整数。共 $2$ 组。

前置知识点

接下来学习