二元一次不定方程

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

$$a x + b y = c$$

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

解法

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

$$\begin{cases} x = x_0 + \dfrac{b}{(a, b)}s, \\ y = y_0 - \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.$$

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

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

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

$$a x' + b y' = 1.$$

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

示例

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

因为$(28, 92) = 4 \mid 52$，所以原方程有解。原方程化为$7x+23y=13$，先解方程$7x'+23y'=1$，对$(23, 7)$做辗转相除，有$23 = 3 \times 7 + 2 \qquad 7 = 3 \times 2 + 1.$
于是$1 = 7 - 3 \times 2 = 7 - 3 \times (23 - 3 \times 7) = 10 \times 7 - 3 \times 23.$
于是题目中的方程一组特解为$(x_0, y_0) = 13 (10, -3) = (130, -39)$，所有的解为

$$\begin{cases} x = 130 + 23s, \\ y = -39 - 7s, \end{cases} \quad s \in \Z.$$

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

正解（非负解）问题

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

$$a x + b y = c$$

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

$$\begin{cases} x = x_0 - \dfrac{b}{(a, b)}s, \\ y = y_0 + \dfrac{a}{(a, b)}s, \end{cases} \quad s \in \Z.$$

中取充分大的$s$即可。

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

而如果$x = 0$或$y=0$，必须满足$b \mid c$或$a \mid c$。同样假设$a,b,c$同号，那么当$c > ab$时原不定方程有正解，且解数为$- \left[-\dfrac{c}{ab}\right]-1$或$-\left[-\dfrac{c}{ab}\right]$，而当$c = ab$时不定方程无正解。要求出这些解，只需在解的通式中令两个未知元大于零即可。

$n$元一次的不定方程可以化为$n-1$个二元一次不定方程求解，其自由因子有$n-1$个。求解的相关方法参看上一节。

上下节

• 上一节：不定方程
• 下一节：Pythagoras 方程