我國古代有過一個著名的“百雞問題”： “今有雞翁一，值錢伍；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁、母、雛各幾何？” ——《張邱建算經》 大概意思是說公雞五元一只，母雞三元一只，小雞一元三只，問100元如何買100只雞?
若設公雞x只，母雞y只，小雞z只，則有：
x+y+z=100
5x+3y+z/3=100
消去未知數z，得到 -14x -8y = -200,化簡后得 7x + 4y = 100
這個方程未知數個數多于方程數，而且要求整數解，應該如何解決呢？
像這樣的未知數個數多于方程個數的方程，我們稱作不定方程。(又叫丟番圖方程,求解不定方程又叫丟番圖分析)
本篇文章將向大家介紹二元一次不定方程的整數解的求法并將給出推導過程和證明。先向大家介紹一些基本概念。
不定方程：
未知數個數多于方程個數的方程叫不定方程。
二元一次不定方程是指形如 ax + by = c的方程。其中x、y為未知數，a、b、c皆為整數。
整除：
若存在一個整數q，使得整數a、b 滿足：a=bq，就稱b整除a，記作b|a。
最大公因數：
能整除a、b的最大正整數叫a、b的最大公因數。記作(a,b)。例如：(15,33)=3。
特別的，如果(a,b)=1,我們就稱a、b互質。一般互質就記作(a,b)=1,有時互質也記作a⊥b。
【引論】二元一次不定方程 ax + by = c 有整數解的充要條件為(a,b)|c。
證：必要性：設(a,b)=d,并設a=Ad,b=Bd.此時顯然有(A,B)=1.
此時我們有 Adx+Bdy = c
則d(Ax+By)=c，故只有當d|c時，原方程才有整數解。
關于其充分性，我們將在下面證明。
另外，對于ax+by=c,一般我們總是假設有(a,b)=1,否則就兩邊同時除以(a,b)=d 使(a/d,b/d)=1.如果c/d不為整數，我們討論過了，原方程一定無整數解。
【引理 2】（輾轉相除法）
a、b、r皆為正整數，如果存在整數q，使得a=bq+r，且0≤r＜b,就稱這個r為最小非負剩余，也叫a除以b的余數。
此時一定有(a,b) = (b,r)。
證：設(a, b)=d, 則 d|a, d|b, 故有d|(a-bq)
又a - bq = r,得到d|r.又因為d|b,則d是b、r的公因數但不一定是最大公因數 ，有d≤(b, r)。
設(b,r)=D, 則 D|b, D|r, 故D|a.則D是a、b的公因數但不一定是最大公因數，有D≤(a, b)。
即d≤D, 且D≤d, 此時只能有D=d,證畢。
這是一種求兩個數的最大公因數的方法，叫做輾轉相除法或Euclid(歐幾里得)算法。
【引理 1】（引論的證明）：若(a,b)=1,則 ax + by = 1 一定有整數解。
證：①：若M、N是兩個能寫成ax+by的數，那么 jM + kN 一定也能寫成ax+by的形式。其中j、k為非0整數。
證①：
設M = ax + by, N = aX + bY
則jM + kN = jax + jby + kaX + kbY = a(jx + kX) + b(jy + kY),其中jx+kX、jy+kY也是整數。①證畢。
②：不妨假設a>b, 此時有
a = b×q1 + r1 (0≤r1 ＜b )
b = r1×q2 + r2 (0≤r2 ＜r1)
r1 = r2×q3 + r3 (0≤r3＜r2)
r2 = r3×q4 + r4 (0≤r4＜r3)
r3 = r4×q5 + r5 (0≤r5＜r4)
……
r(n-1) = r(n)×q(n+1)
由于b>r1>r2>r3>r4>r5>……>r(n)，余數是不斷減小的，所以經過有限步驟后余數總會為0。
又由輾轉相除法得到(a,b)=(b,r1)=(r1,r2)=(r2,r3)=……=(r(n-1),r(n))=r(n)，又由(a,b)=1,則r(n)=1.
③：改寫上面的式子：
r1 = a - b×q1
r2 = b - r1×q2
r3 = r1 - r2×q3
……
r(n) = r(n-2) - q(n)×r(n-1)
a、b本身是形如ax+by的數（因為a=a*1+b*0，b=a*0+b*1），故易知r1也是形如ax+by的數。那么r2也是。以此類推，得到r(n)也是形如ax+by的數，而r(n)=1，故存在一組x、y，使得ax+by=1,證畢。
【引理 3】如果{x=X, y=Y}是 ax + by = c的一組解，那么{x = X-bt, y = Y+at}是方程的所有解。其中t是任意整數。
證：代入原方程即可。
【引理 4】如果a、b互質，則 ax+by=c 一定有整數解。
證：考慮 ax+by = 1,由于(a,b)=1,以及引理1，知道一定存在一對x、y使得ax+by=1.
那么兩邊同時相乘以c，則
a(cx) + b(cy) = c，其中cx、cy均為整數，證畢。
也就是說，要求ax+by=c的解，應該先求ax+by=1的解。
下面我將向大家說明求出ax+by=1中的x、y的具體方法。
【例1】7x+4y=100 (百雞問題中的方程)
解：
先解7x+4y=1.由于(7,4)=1,知道方程一定有整數解。
用引理1中介紹的方法，對7和4進行輾轉相除：
7 = 4*1 + 3, 4 = 3*1 + 1
則 1 = 4 - 3 = 4 - (7 - 4) = 4*2 - 7 = -7 + 4*2
故 x = -1, y = 2 是7x+4y=1的一組解。故 x = -100, y = 200 是7x+4y=100的一組解。
則 {x = -100 - 4t, y = 200 + 7t} 是7x+4y=100的所有解。其中t為任意整數。
根據原題目，得到 z = 100 - x - y = -3t，又因為雞的數量不可能是負數，故得到不等式：
-100 - 4t ≥0
200 + 7t ≥0
- 3t ≥0
結合t是整數，解得 -28 ≤t≤ -25，即 t = -25,-26,-27,-28.
則我們得到這個問題的4組解答：
{x = 0, y = 25, z = 75}
{x = 4, y = 18, z = 78}
{x = 8, y = 11, z = 82}
{x = 12, y = 3, z = 85}
這個方法適用于所有這樣的一次不定方程（組）。
同時還適用于求一次同余方程 ax ≡ b (mod m) 的整數解。其中若(a,m)=1,則該同余方程實際上可化為 ax + my = -b 。
（@曹曹無敵 這個方法可以用來寫那個解同余方程的計算機程序。。）
這篇文章如有錯誤和遺漏，歡迎大家提出指正。
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
