最后更新: 2023-10-24 14:11 查看: 326 次反馈刷题

二元一次不定方程

在数论中，二元一次不定方程是形如

$$
a x+b y=c
$$

的不定方程，其中 $a, b$ 是整数，这个方程是关于整数变量 $x, y$ 的方程。

## 解法

定理：上述方程有解的充要条件是 $(a, b) \mid c$ ，在有解时，若已知方程有一组特解 $\left(x_0, y_0\right)$ ，那么它的所有解的形式是

$$
\left\{\begin{array}{l}
x=x_0+\frac{b}{(a, b)} s, \\
y=y_0-\frac{a}{(a, b)} s,
\end{array} s \in \mathbb{Z} .\right.
$$

因此，我们仅需求出一组特解即可，如果方程有解，我们总可以将上述方程先做化简，为

$$
\frac{a}{(a, b)} x+\frac{b}{(a, b)} y=\frac{c}{(a, b)}
$$

下面，我们总假设 $(a, b)=1$. 做变换 $x=c x^{\prime}, y=c y^{\prime}$ ，于是，原方程等价于

$$
a x^{\prime}+b y^{\prime}=1 \text {. }
$$

当式子简单时可以直接看出一组解，其实，注意到这就是在辗转相除法中介绍的贝祖等式，它可以由辗转相除的方法求出一组特解 $\left(x_0^{\prime}, y_0^{\prime}\right)$ ，进而带入所作的变换中，有原方程的特解 $\left(x_0, y_0\right)=\left(c x_0^{\prime}, c y_0^{\prime}\right)$

## 示例

求方程 $28 x+92 y=52$ 的所有整数解。

因为 $(28,92)=4 \mid 52$ ，所以原方程有解。原方程化为 $7 x+23 y=13$ ，先解方程 $7 x^{\prime}+23 y^{\prime}=1$ ，对 $(23,7)$做辗转相除，有 $23=3 \times 7+2 \quad 7=3 \times 2+1$.

于是 $1=7-3 \times 2=7-3 \times(23-3 \times 7)=10 \times 7-3 \times 23$.
于是题目中的方程一组特解为 $\left(x_0, y_0\right)=13(10,-3)=(130,-39)$ ，所有的解为

$$
\left\{\begin{array}{l}
x=130+23 s, \\
y=-39-7 s,
\end{array} \quad s \in \mathbb{Z} .\right.
$$

当数字过大时，可以不用先找 $(a, b)$ ，也不用判断是否有解，直接做辗转相除即可。

## 正解的问题

在实际应用场合中，有时要求方程的解取正数或非负数，这时由以上方法取得的解有一部分可能不适用，这时就要对方程做更精细的讨论。对于方程

$$
a x+b y=c
$$

当 $a, b$ 异号 (不妨假设 $a>0$ ) 时，方程总有无穷多组非负解，只需要在解的通式

$$
\left\{\begin{array}{l}
x=x_0-\frac{b}{(a, b)} s, \\
y=y_0+\frac{a}{(a, b)} s,
\end{array} \quad s \in \mathbb{Z} .\right.
$$

中取充分大的 $s$ 即可。
当 $a, b$ 同号时，只有 $a, b, c$ 同号时才有可能存在非负解，实际上可以证明：当 $c>a b-a-b$ 时不定方程有非负解，解的个数为 $\left[\frac{c}{a b}\right]$ 或 $\left[\frac{c}{a b}\right]+1$ (需验证不同情形)，而当 $c=a b$ 时不定方程无非负解。要求出这些解，只需在解的通式中令两个未知元大于等于零即可。

而如果 $x=0$ 或 $y=0$ ，必须满足 $b \mid c$ 或 $a \mid c$ 。同样假设 $a, b, c$ 同号，那么当 $c>a b$ 时原不定方程有正解，且解数为 $-\left[-\frac{c}{a b}\right]-1$ 或 $-\left[-\frac{c}{a b}\right]$ ，而当 $c=a b$ 时不定方程无正解。要求出这些解，只需在解的通式中令两个未知元大于零即可。
$n$ 元一次的不定方程可以化为 $n-1$ 个二元一次不定方程求解，其自由因子有 $n-1$ 个。求解的相关方法参看上一节。

开VIP会员

非会员每天6篇，会员每天16篇，VIP会员无限制访问

题库训练自我测评投稿

上一篇：梅森素数

下一篇： Pythagoras 方程

本文对您是否有用？有用 (0) 无用 (0)