1.2　二元一次不定方程的非负解和正解

下面我们来讨论当二元一次不定方程（4）可解时，它的非负解和正解问题.由通解公式（5）知，在已知一组特解后，这可归结为去确定参数t的值，使x₁，x₂均为非负或正.显见，当a₁，a₂异号时，不定方程（4）可解时总有无穷多组非负解或正解.所以，只要讨论a₁，a₂均为正的情形.先来讨论非负解.

定理4设a₁，a₂及c均为正整数，（a₁，a₂）=1，那么，当c＞a₁a₂-a₁-a₂时，不定方程（4）有非负解，解数等于［c/（a₁a₂）］或［c/（a₁a₂）］+1；当c=a₁a₂-a₁-a₂时，不定方程（4）没有非负解。

证由于（a₁，a₂）=1，所以方程（4）必有解.设x₁，0，x_2，0是方程（4）的一组特解.由通解公式（5）知，所有非负解x₁，x₂由满足以下条件的参数t给出：

-［x_1，0/a₂］-{x_1，0/a₂}=-x_1，0/a₂≤t≤x_2，0/a₁=［x_2，0/a₁］+{x_2，0/a₁}，

由此及［x］的定义、0≤{x}<1知，上式即

-［x_1，0/a₂］≤t≤［x_2，0/a₁］.（11）

因此，方程（4）的非负解的组数

N₀=［x_1，0/a₂］+［x_2，0/a₁］+1，（12）

即（为什么）

N₀=［x_1，0/a₂+x_2，0/a₁］+1+{x_1，0/a₂+x_2，0/a₁}-{x_1，0/a₂}-{x_2，0/a₁}.

由此及0≤{x}<1推得（为什么）

［x_1，0/a₂+x_2，0/a₁］≤N₀≤［x_1，0/a₂+x_2，0/a₁］+1，

且上式中等号有且仅有一个成立.由于x_1，0，x_2，0是特解，所以

x_1，0/a₂+x_2，0/a₁=c/（a₁a₂）.

由以上两式得

N₀=［c/（a₁a₂）］或［c/（a₁a₂）］+1.

当c＞a₁a₂-a₁-a₂这个有非负解的充分条件是怎样得来的，请读者考虑.时，

1-1/a₁-1/a₂＜c/a₁a₂=x_1，0/a₂+x_2，0/a₁=［x_1，0/a₂］+｛x_1，0/a₂｝+［x_2，0/a₁］+｛x_2，0/a₁｝≤［x_1，0/a₂］+［x_2，0/a₁］+（a₁-1）/a₁+（a₂-1）/a₂，

最后一步用到了对正整数n及整数m，必有｛m/n｝≤（n-1）/n.由此即得

［x_1，0/a₂］+［x_2，0/a₁］＞-1，

进而由此及式（12）推出N₀＞0，即这时必有非负解.

当c=a₁a₂-a₁-a₂时，若有非负解x₁，x₂，则有

a₁（x₁+1）+a₂（x₂+1）=a₁a₂，（13）

由此及（a₁，a₂）=1，利用第一章4定理6可得

a₁|x₂+1，a₂|x₁+1.

由于x₁≥0，x₂≥0，所以必有x₂+1≥a₁≥1，x₁+1≥a₂≥1.由此及式（13）推出

a₁a₂≥2a₁a₂.

但这是不可能的.所以，当c=a₁a₂-a₁-a₂时，方程（4）没有非负解.定理证毕.

显见，要有x₁=0或x₂=0的解，必须满足a₂｜c或a₁｜c.下面用类似的方法来讨论正解.

定理5设a₁，a₂及c均为正整数，（a₁，a₂）=1，那么，当c＞a₁a₂时，方程（4）有正解，解数等于-［-c/（a₁a₂）］-1或-［-c/（a₁a₂）］；当c=a₁a₂时，方程（4）无正解.

证由于（a₁，a₂）=1，方程（4）必有解.设x₁，0，x_2，0是方程（4）的一组特解.由通解公式（5）知，所有正解x₁，x₂由满足以下条件的参数t给出

-［x_1，0/a₂］-{x_1，0/a₂}=-x_1，0/a₂＜t＜x_2，0/a₁=-［-x_2，0/a₁］-{-x_2，0/a₁}，

由此及［x］的定义、0≤{x}<1知，上式即

［-x_1，0/a₂］+1≤t≤-［-x_2，0/a₁］-1.（14）

因此，正解的组数

N₁=-［-x_1，0/a₂］-［-x_2，0/a₁］-1，（15）

即（为什么）

N₁=-［-x_1，0/a₂-x_2，0/a₁］-1-{-x_1，0/a₂-x_2，0/a₁}+{-x_1，0/a₂}+{-x_2，0/a₁}.

由此及0≤{x}<1推得

-［-x_1，0/a₂-x_2，0/a₁］-1≤N₁≤-［-x_1，0/a₂-x_2，0/a₁］.

由于x_1，0，x_2，0是解，所以

-x_1，0/a₂-x_2，0/a₁=-c/（a₁a₂）.

由以上两式即得

N₁=-［-c/（a₁a₂）］-1或-［-c/（a₁a₂）］.

当c＞a₁a₂时，-［-c/（a₁a₂）］≥2，因此N₁≥1即必有正解.当c=a₁a₂时，若有正解x₁，x₂，则有

a₁x₁+a₂x₂=a₁a₂，（16）

由此及（a₁，a₂）=1，利用第一章4定理6可得

a₂|x₁，a₁|x₂.

由于x₁≥1，x₂≥1，所以必有x₁≥a₂≥1，x₂≥a₁≥1.由此及式（16）推出

a₁a₂≥2a₁a₂.

但这是不可能的.所以当c=a₁a₂时，方程（4）无正解.证毕.

应该指出：方程（4）有正解的充分必要条件是方程

a₁x₁+a₂x₂=c-a₁-a₂

有非负解.因此，定理4和定理5只要证明了一个就能推出另一个，详细的论证留给读者.此外，这两个定理中的解数公式（12）和（15）在一些情况下比定理中的结论更有用，当然，这需要先找出一组特解（并不一定要是非负解或正解）.下面来举几个例.

例7求5x₁+3x₂=52的全部正解.

解x₁=8，x₂=4是一组特解，由式（5）和（14）知全部正解是：

x₁=8+3t，x₂=4-5t，

-2=［-8/3］+1≤t≤-［-4/5］-1≤0.

所以共有三组正解：8，4；5，9；2，14.容易看出x₁=0或x₂=0都不可能是解，因此这也是全部非负解.

例8证明：101x₁+37x₂=3189有正整数解.

证这里c=3189＜a₁a₂=101·37，所以从定理5的结论不能确定方程是否有正解（当然可推出至多有一个）.因此需要利用式（15）（或（14））.可以求出x₁=11·3189，x₂=-30·3189是一组特解（请读者自己去求），由式（15）知解数等于

-［-11·3189/37］-［30·3189/101］-1=949-947-1=1.

即方程恰有一组正解.请读者自己去求出这组正解.

例9鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一.百钱买百鸡.问：鸡翁、母雏各几何？

解以x₁，x₂，x₃分别代表鸡翁、鸡母、雏鸡的数目，由条件可得下面的不定方程组

我们要求这不定方程组的非负解.消去x₃可得

7x₁+4x₂=100.

先求这不定方程的非负解.x₁=0，x₂=25是一组特解.由式（5）及定理4知，它的全部非负解是：

x₁=0+4t，x₂=25-7t，

0=-［0/4］≤t≤［25/7］=3.

即是0，25；4，18；8，11；12，4.因此所买的鸡的各种可能的情形是下表：

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

解由例6知通解公式是

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

所以给出非负解的t₁，t₂是

5+2t₁+6t₂≥0，-5-3t₁-6t₂≥0，6-5t₂≥0.

由此得

-5/3-2t₂≥t₁≥-5/2-3t₂，t₂≤6/5，

进而有

-5/6≤t₂≤6/5.

所以，t₂=0，1.容易算出，t₂=0时，t₁=-2；t₂=1时，t₁=-4，-5.由此从通解公式求出所有非负解是

1，1，6；3，1，1；1，4，1.

由例5所得的通解公式也可得到同样的结果.

求非负解或正解的问题可推广到一般的n元一次不定方程

a₁x₁+a₂x₂+…+a_nx_n=c，

这里a₁，…，a_n是n个互素的正整数.要去求出正整数

c₁=c₁（a₁，a₂，…，a_n）或c₂=c₂（a₁，a₂，…，a_n），

使得上述不定方程为c>c₁或c>c₂时一定有非负解或正解.当n=2时，上面已证明c₁=a₁a₂-a₁-a₂，c₂=a₁a₂.当n>2时，这是一个未解决的著名问题，它称为Frobenius问题.当然对具体问题或一些特殊情形是可以处理的.