1.1　一次不定方程的求解

定理1不定方程（1）有解的充分必要条件是它的系数的最大公约数（a₁，…，a_k）|c.进而，不定方程（1）有解时，它的解和不定方程

的解相同，这里g=（a₁，…，a_k）.

证必要性显然.下面来证充分性.若g|c，设c=gc₁.由第一章4定理8知，必有整数y_1，0，…，y_k，0，使得

a₁y_1，0+…+a_ky_k，0=g.（3）

因此x₁=c₁y_1，0，…，x_k=c₁y_k，0即为（1）的一组解，这就证明了充分性.由于（1）有解时必有g|c，而这时不定方程（1）和（2）是同一个方程，这就证明了后一结论.

定理1表明讨论不定方程（1）的关键是讨论它的系数的最大公约数g.关于两个变数的情形有下面更精确的定理.

定理2设二元一次不定方程

a₁x₁+a₂x₂=c（4）

有解，x_1，0，x_2，0是它的一组解，那么它的所有解为

证容易直接验证由式（5）给出的x₁，x₂，对所有整数t都满足不定方程（4）.反过来，设x₁，x₂是（4）的一组解.我们有

a₁x₁+a₂x₂=c=a₁x_1，0+a₂x_2，0，

进而有

a₁（x₁-x_1，0）=-a₂（x₂-x_2，0），

例1求10x₁-7x₂=17的全部解.

解容易看出，（10，7）=1，所以方程有解.由视察法可得x_1，0=1，x_2，0=-1是一组特解.因此全部解是

x₁=1-7t，x₂=-1-10t，t=0，±1，±2，….

例2求18x₁+24x₂=9的解.

解由（18，24）=6｜/9知无解.

求解不定方程（4），必须（i）求出最大公约数g=（a₁，a₂），并判断是否有g|c；（ii）若g|c，即有解，则设法去求出一组特解x_1，0，x_2，0.由定理1及3定理5知，我们可以用辗转相除法来求特解.下面我们通过具体例子来介绍一种判定方程是否有解、及有解时求出其解的直接算法.这种算法对k＞2的情形也适用.

例3求907x₁+731x₂=2107的解.

解若有解，则731必整除-907x₁+2107，所以由原方程得

（注：以上两步是，先解出系数绝对值较小的变数，这里是x₂，再作变数替换，把x₂变为x₃（为什么）.这就得到一个新的不定方程：176x₁+731x₃=-86.把原来关于x₁，x₂的不定方程转化为关于x₁，x₃的不定方程，且其系数绝对值比原方程小.下面就是反复这样做.）

这样就求出了全部解：

x₁=-258+731x₆，x₂=323-907x₆，x₆=0，±1，±2，….

细心的读者不难发现，这种解不定方程的算法实际上是对整个不定方程用辗转相除法（见第一章3），依次化为等价的不定方程，直至得到有一个变元的系数为±1的不定方程为止（在上例中是x₅-13x₆=-5），这样的不定方程是可以直接解出的（这里是x₅=-5+13x₆，x₆=0，±1，±2，…）.再依次反推上去，就得到原方程的通解.为了减少运算次数，在用带余数除法时，我们总取绝对最小余数.如果不定方程无解，则在施行这种算法时，到某一步就会直接看出，下面来举一个例子.

例4求117x₁+21x₂=38的解.

解由原方程得

最后一式表明：x₃，x₄不可能同时为整数，所以不定方程无解.

下面来举一个用这种算法解三元一次不定方程的例子.

例5求15x₁+10x₂+6x₃=61的全部解.

解x₃的系数的绝对值最小，我们把原方程化为

解得x₁=1+2x₅，x₅=0，±1，±2，….

反推上去依次解出

x₂=3x₄+x₁+x₅=1+3x₄+3x₅，x₄，x₅=0，±1，±2，….x₃=-2x₁-2x₂+10+x₄=6-5x₄-10x₅，x₄，x₅=0，±1，±2，….

这就得到了原不定方程的通解，其中含有两个参数x₄，x₅.

下面的定理表明：一般的k元一次不定方程可化为解由k-1个二元一次不定方程构成的方程组，且它的通解中恰有k-1个参数.

定理3设g₁=a₁，g₂=（g₁，a₂）=（a₁，a₂），g₃=（g₂，a₃）=（a₁，a₂，a₃），…，g_j=（a₁，…，a_j），…，g_k=（g_k-1，a_k）=（a₁，…，a_k），那么不定方程（1）等价于下面的有2（k-1）个整数变数x₁，…，x_k，y₂，…，y_k-1，k-1个方程的不定方程组：

当方程（1）有解时，它的通解由有k-1个参数的线性（即一次）表达式给出.

证先来证等价性.若x₁，…，x_k，y₂，…，y_k-1是方程组（6）的解，则显见x₁，…，x_k是（1）的解.反之，若x₁，…，x_k是（1）的解，则取

显见，y_j是整数，且x₁，…，x_k，y₂，…，y_k-1是（6）的解.由定理1容易看出，方程组（6）的第一个方程和方程（1）一样，有解的充分必要条件是g_k|c.而（6）的其余的方程，当把y_j看做参数（取整数值）时，每个变数为y_j-1，x_j的二元一次不定方程

g_j-1y_j-1+a_jx_j=g_jy_j（7）

总是可解的（注：这里当j=2时，规定x₁=y₁.），这里j依此取k-1，…，2.一定可以找到y^（0）_j-1，x^（0）_j，使

g_j-1y^（0）_j-1+a_jx^（0）_j=g_j，（8）

这样y_jy^（0）_j-1，y_jx^（0）_j就是（7）的一组特解，由定理2知，（7）的通解是

t_j-1=0，±1，±2，…（2≤j≤k-1）.

当（1）有解，即g_k|c时，方程组（6）的第一个方程可解，且由定理2知，其通解是（y_k-1，0，x_k，0是一组特解）

t_k-1=0，±1，±2，….

式（10）已经给出了y_k-1和x_k的参数t_k-1的表达式（注：这里所说的参数表达式都是线性（即一次）的，下同.）.由y_k-1的参数表达式及式（9）（j=k-1）可得到y_k-2和x_k-1的参数t_k-1，t_k-2的表达式；进而由y_k-2的参数表达式及式（9）（j=k-2）可得到y_k-3和x_k-2的参数t_k-1，t_k-2，t_k-3的表达式；依次就得到y_j-1和x_j（j=k-3，…，2）的参数t_k-1，…，t_j-1的表达式.这就给出了方程组（6）变元x₁，…，x_k，y₂，…，y_k-1（注意x₁=y₁）的通解公式（为什么），其中有k-1个参数t₁，…，t_k-1.显见，其中的一部分——x₁，…，x_k的参数表示式就给出了不定方程（1）的通解公式（为什么）.证毕.

以上定理的证明读者可能会感到“复杂”，不习惯.下面仍以例5为例，说明如何用定理3的方法来解k（＞2）元一次不定方程.读者可以先看下面的例6，有一个感性认识后，再看定理3的证明.

例6求15x₁+10x₂+6x₃=61的解.

解用定理3的方法来解.a₁=15，a₂=10，a₃=6，所以g₁=a₁=15，g₂=（a₁，a₂）=（15，10）=5，g₃=（g₂，a₃）=（5，6）=1.因此这不定方程等价于4个变数、两个方程的不定方程组：

15x₁+10x₂=5y₂的通解是

x₁=y₂+2t₁，x₂=-y₂-3t₁，t₁=0，±1，….

5y₂+6x₃=61的通解是

y₂=5+6t₂，x₃=6-5t₂，t₂=0，±1，….

消去y₂就得到原不定方程的通解：

x₁=5+2t₁+6t₂，x₂=-5-3t₁-6t₂，x₃=6-5t₂，

t₁，t₂=0，±1，….

比较得到的两个通解公式，可以发现含有的参数个数都是两个，但具体的表示形式却有很大不同，这是由于所用的解法不同引起的，而实质上是一样的.关于这一点将在习题中讨论.

定理3已经涉及比较简单的一次不定方程组的问题，对这一问题的讨论比较繁，要用到一些整数矩阵的知识，这里不作进一步讨论了.有兴趣的读者可参看文献［3］，［5］.有一些不定方程要求它的正解或非负解，即变数取正整数或非负整数的解，这在应用中是很常见的.例如下面的例9.下面我们将讨论两个变数的情形.