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問題.當然對具體問題或一些特殊情形是可以處理的.