二元一次不定方程

一次不定方程
术语名称	一次不定方程
英语名称	linear Diophatine equation

二元一次不定方程是最简单的不定方程，具有形式 [math]\displaystyle{ ax + by = c }[/math] ，其中 [math]\displaystyle{ a, b, c }[/math] 是给定整数。

定义

形如 [math]\displaystyle{ ax + by = c }[/math] ，其中 [math]\displaystyle{ a, b, c }[/math] 为整数的不定方程，称为二元一次不定方程。

解

有解条件

（即裴蜀定理）

二元一次不定方程 [math]\displaystyle{ ax + by = c }[/math] 有整数解，当且仅当 [math]\displaystyle{ \operatorname{gcd}(a, b) \mid c }[/math] 。

解的结构

二元一次不定方程 [math]\displaystyle{ ax + by = c }[/math] 的解之间满足：若 [math]\displaystyle{ \begin{cases}x = x_0 \\ y = y_0 \end{cases} }[/math] 是方程的一个解，则对任意整数 [math]\displaystyle{ t }[/math] ，有 [math]\displaystyle{ \begin{cases} x= x_0 + bt \\ y = a_0 - at \end{cases} }[/math] 也是方程的一个解。

有解的情况下，必然可以对 [math]\displaystyle{ a, b, c }[/math] 同时约去 [math]\displaystyle{ \operatorname{gcd}(a, b) }[/math] ，得到新的方程使得 [math]\displaystyle{ \operatorname{gcd}(a, b) = 1 }[/math] 。因此不妨设 [math]\displaystyle{ \operatorname{gcd}(a, b) = 1 }[/math] 。

此时可以反过来证明，所有的解都满足上述关系。此时，称某个满足原不定方程的 [math]\displaystyle{ \begin{cases}x = x_0 \\ y = y_0 \end{cases} }[/math] 为不定方程的一个特解，并称 [math]\displaystyle{ \begin{cases} x= x_0 + bt \\ y = a_0 - at \end{cases} }[/math] ，其中 [math]\displaystyle{ t }[/math] 取任意整数， [math]\displaystyle{ \operatorname{gcd}(a, b) = 1 }[/math] ，为不定方程的整数通解。

具体解

对普遍情形，也就是考虑任意 [math]\displaystyle{ a, b }[/math] ，并从式中约去 [math]\displaystyle{ \operatorname{gcd}(a, b) }[/math] 的情形，有：

可通过扩展 Euclid 算法求取其最大公因数及整系数线性组合的系数，即 [math]\displaystyle{ u a + v b = \operatorname{gcd}(a, b) }[/math] 的一组 [math]\displaystyle{ u, v }[/math] ，此时不定方程有特解 [math]\displaystyle{ \begin{cases}x_0 = u_0 \cdot \frac{c}{\operatorname{gcd}(a,b)} \\ y_0 = v_0 \cdot \frac{c}{\operatorname{gcd}(a,b)}\end{cases} }[/math] 。

同时，通解为 [math]\displaystyle{ \begin{cases} x= x_0 + \frac{b}{\operatorname{gcd}(a,b)} t \\ y = a_0 - \frac{a}{\operatorname{gcd}(a,b)} t \end{cases} }[/math] 。

非负解、正解

非负解

对不定方程 [math]\displaystyle{ ax + by = c }[/math] ，设其中 [math]\displaystyle{ a, b, c }[/math] 均为正整数，且 [math]\displaystyle{ \operatorname{gcd}(a,b) = 1 }[/math] ：

若 [math]\displaystyle{ c \gt a b - a - b }[/math] ，不定方程有非负整数解，且非负整数解的个数等于 [math]\displaystyle{ \left\lfloor \tfrac{c}{a b} \right\rfloor }[/math] 或 [math]\displaystyle{ \left\lfloor \tfrac{c}{a b} \right\rfloor + 1 }[/math] 。

若 [math]\displaystyle{ c = a b - a - b }[/math] ，不定方程没有非负解。

以上为充分条件，取小于号时无法通过这一比较判断。

若此时已知一组特解 [math]\displaystyle{ x_0, y_0 }[/math] ，则非负解的组数为 [math]\displaystyle{ \left\lfloor \tfrac{x_0}{b} \right\rfloor + \left\lfloor \tfrac{y_0}{a} \right\rfloor + 1 }[/math] 。

正解

对不定方程 [math]\displaystyle{ ax + by = c }[/math] ，设其中 [math]\displaystyle{ a, b, c }[/math] 均为正整数，且 [math]\displaystyle{ \operatorname{gcd}(a,b) = 1 }[/math] ：

若 [math]\displaystyle{ c \gt a b }[/math] ，不定方程有正整数解，且正整数解的个数等于 [math]\displaystyle{ \left\lceil \tfrac{c}{a b} \right\rceil - 1 }[/math] 或 [math]\displaystyle{ \left\lceil \tfrac{c}{a b} \right\rceil }[/math] 。

若 [math]\displaystyle{ c = a b }[/math] ，不定方程没有正解。

以上为充分条件，取小于号时无法通过这一比较判断。

若此时已知一组特解 [math]\displaystyle{ x_0, y_0 }[/math] ，则非负解的组数为 [math]\displaystyle{ \left\lceil \tfrac{x_0}{b} \right\rceil + \left\lceil \tfrac{y_0}{a} \right\rceil - 1 }[/math] 。

不定方程
一次	一次不定方程	二元一次不定方程、多元一次不定方程
齐次	齐次不定方程	商高方程、Fermat 大定理
指数	-
其他结论	Lagrange 四平方和定理	Fermat 二平方定理