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