不定方程的解法

1、二元一次不定方程的解法求a * x + b * y = n的整數(shù)解。1、先計算Gcd(a,b),若n不能被Gcd(a,b)整除，則方程無整數(shù)解；否則，在方程兩邊同時除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此時Gcd(a',b')=1;2、 利用上面所說的歐幾里德算法求出方程a' * x + b' * y = 1的一組整數(shù)解xO,yO，則n' * x0,n' * y0是方程a' * x + b' * y = n'的一組整數(shù)解；3、 根據(jù)數(shù)論中的相關(guān)定理，可得方程

2、a' * x + b' * y = n'的所有整數(shù)解為：x = n' * x0 + b' * ty = n' * y0 - a' * t（t為整數(shù)）那么，一般來說，它的解往等，它們的解是不確定的.像不定方程(組)是數(shù)論中的上面的解也就是 a * x + b * y = n的全部整數(shù)解。我們知道，如果未知數(shù)的個數(shù)多于方程的個數(shù), 往是不確定的，例如方程x-2y=3， 方程組 這類方程或方程組就稱為不定方程或不定方程組. 一個古老分支，其內(nèi)容極其豐富我國我們知道，如果未知數(shù)的個數(shù)多于方程的個數(shù)，那么，一般來說，它的解往往是不確定的，例如方程x

3、-2y=3，方程組等，它們的解是不確定的.像這類方程或方程組就稱為不定方程或不定方程 組.不定方程(組)是數(shù)論中的一個古老分支，其內(nèi)容極其豐富.我國對不定方程 的研究已延續(xù)了數(shù)千年，“百雞問題”等一直流傳至今，“物不知其數(shù)”的解法 被稱為中國剩余定理.近年來，不定方程的研究又有新的進展.學(xué)習(xí)不定方程， 不僅可以拓寬數(shù)學(xué)知識面，而且可以培養(yǎng)思維能力，提高數(shù)學(xué)解題的技能.我們先看一個例子.例 小張帶了 5角錢去買橡皮和鉛筆，橡皮每塊 3分，鉛筆每支1角1分， 問5角錢剛好買幾塊橡皮和幾支鉛筆？解 設(shè)小張買了 x塊橡皮，y支鉛筆，于是根據(jù)題意得方程3x+11y=50.這是一個二元一次不定方程.從方程

4、來看，任給一個x值，就可以得到一個 y值，所以它的解有無數(shù)多組.但是這個問題要求的是買橡皮的塊數(shù)和鉛筆的支數(shù)， 而橡皮的塊數(shù)與鉛筆的 支數(shù)只能是正整數(shù)或零，所以從這個問題的要求來說，我們只要求這個方程的非 負(fù)整數(shù)解.因為鉛筆每支1角1分，所以5角錢最多只能買到4支鉛筆，因此，小張買 鉛筆的支數(shù)只能是0, 1, 2, 3, 4支，即y的取值只能是0, 1, 2, 3, 4這五個.若y = 則"弓，不是整數(shù)，不合題意；若y = h則耳= 13,符合題意；若y = 2, PJjx = , "F是整數(shù)，不合題意弓若y=3，則x=17/3，不是整數(shù)，不合題意； 若y=4,則x=2,符

5、合題意.所以，這個方程有兩組正整數(shù)解，即z = 2t fx = 13y =4? ly = 1.也就是說，5角錢剛好能買2塊橡皮與4支鉛筆，或者13塊橡皮與1支鉛 筆.像這個例子，我們把二元一次不定方程的解限制在非負(fù)整數(shù)時，那么它的解就確定了.但是否只要把解限制在非負(fù)整數(shù)時，二元一次不定方程的解就一定能 確定了呢？不能！現(xiàn)舉例說明.例求不定方程x-y=2的正整數(shù)解.解我們知道：3-1=2 , 4-2=2, 5-3=2 ,，所以這個方程的正整數(shù)解有無數(shù) 組，它們是其中n可以取一切自然數(shù).因此，所要解的不定方程有無數(shù)組正整數(shù)解，它的解是不確定的.上面關(guān)于橡皮與鉛筆的例子，我們是用逐個檢驗的方法來求它

6、們的非負(fù)整數(shù) 解的，但是這種方法在給出的數(shù)比較大的問題或者方程有無數(shù)組解的時候就會遇 到麻煩.那么能不能找到一個有效而又方便的方法來求解呢？我們現(xiàn)在就來研究 這個問題，先給出一個定理.定理 如果a，b是互質(zhì)的正整數(shù)，c是整數(shù)，且方程ax+by=c 有一組整數(shù)解xo, yo則此方程的一切整數(shù)解可以表示為* =x0 -bty = y0 -Fat,其中 t=0，± 1，± 2，± 3，,.證 因為xo, yo是方程的整數(shù)解，當(dāng)然滿足axo+byo=c，因此a(x o-bt)+b(y o+at)=ax o+byo=c. 這表明x=xo-bt，y=yo+at也是方程的解.設(shè)

7、xz，y/是方程的任一整數(shù)解，則有ax7 +bxz =c.-得a(x / -x o)=b / (y / -y o).由于(a , b)=1 ,所以 a | y/ -y 0,即 y' =yo+at,其中 t 是整數(shù).將 y' =yo+at 代入，即得x/ =xo-bt .因此xz, y/可以表示成x=xo-bt , y=yo+at的形式， 所以x=xo-bt , y=yo+at表示方程的一切整數(shù)解，命題得證.有了上述定理，求解二元一次不定方程的關(guān)鍵是求它的一組特殊解.例1求11x+15y=7的整數(shù)解.解法1將方程變形得7-15y因為x是整數(shù)，所以7-15y應(yīng)是11的倍數(shù).由觀察得

8、xo=2, yo=-1是這個方 程的一組整數(shù)解，所以方程的解為"x = 2 *15t,y = -1+1 It解法2先考察11x+15y=1，通過觀察易得11X(-4)+15 X (3)=1，所以11X(-4X 7)+15 X (3 X 7)=7，可取 xo=-28，yo=21 .從而卜=-28 -15tF21 + 1 比可見，二元一次不定方程在無約束條件的情況下， 通常有無數(shù)組整數(shù)解，由 于求出的特解不同，同一個不定方程的解的形式可以不同， 但它們所包含的全部 解是一樣的.將解中的參數(shù)t做適當(dāng)代換，就可化為同一形式.例2求方程6x+22y=90的非負(fù)整數(shù)解.解 因為(6，22)=2，

9、所以方程兩邊同除以2得3x+11y=45.由觀察知，x仁4, y1=-1是方程3x+11y=1 的一組整數(shù)解，從而方程的一組整數(shù)解為1 = 45X4180,y0 = 45X (. -1J "5由定理，可得方程的一切整數(shù)解為= 180 -lltPjy 二上15 十 3t*因為要求的是原方程的非負(fù)整數(shù)解，所以必有180-llt>0P-45+3t>0.由于t是整數(shù)，由，得15< t < 16,所以只有t=15 , t=16兩種可能.當(dāng)t=15時，x=15，y=0;當(dāng)t=16時，x=4，y=3.所以原方程的非負(fù)整數(shù)解 是例3求方程7x+19y=213的所有正整數(shù)解.分

10、析 這個方程的系數(shù)較大，用觀察法去求其特殊解比較困難，碰到這種情 況我們可用逐步縮小系數(shù)的方法使系數(shù)變小，最后再用觀察法求得其解.解用方程7x+19y=213 的最小系數(shù)7除方程的各項，并移項得“呼= gy+琴.因為x，y是整數(shù)，故3-5y/7=u也是整數(shù)，于是5y+7u=3. T儆*5除此式的 兩邊得3 -7u.3- 2u小y = _ = .u+_.®令學(xué)=* （蝮）,由此得2u+5v=3.由觀察知u=-1 , v=1是方程的一組解.將u=-1 , v=1代入得y=2. y=2 代入得x=25.于是方程有一組解xo=25, yo=2，所以它的一切解為y=2+7t.由于要求方程的正整

11、數(shù)解，所以f25-19t>0.（2 十 7tCL解不等式，得t只能取0, 1 .因此得原方程的正整數(shù)解為卜* |y = 9.當(dāng)方程的系數(shù)較大時，我們還可以用輾轉(zhuǎn)相除法求其特解，其解法結(jié)合例題 說明.例4求方程37x+107y=25的整數(shù)解.解 107=2X 37+33,37=1 X 33+4，33=8X 4+1.為用37和107表示1,我們把上述輾轉(zhuǎn)相除過程回代，得仁33-8X4=37-4- 8X4=37-9X4=37- 9X (37 - 33)=9 X 33-8X 37=9X (107-2X 37)8 X 37= 9X 107-26X 37由此可知x1=-26 , y1=9是方程37x

12、+107y=1的一組整數(shù)解.于是Xo=25X( -26)=-650 , yo=25X 9=225是方程37x+107y=25的一組整數(shù)解.所以原方程的一切整數(shù)解為煜整數(shù).K = _650-107t, y = 225+37tf例5某國硬幣有5分和7分兩種，問用這兩種硬幣支付142分貨款，有多 少種不同的方法？解 設(shè)需x枚7分，y枚5分恰好支付142分，于是7x+5y=142.所以142-7i5=28-x -由于7x< 142,所以x<20,并且由上式知5 | 2(x-1).因為(5，2)=1，所 以5 | x-1，從而x=1, 6，11，16,的非負(fù)整數(shù)解為x=1.r -1 - 16

13、,Ay = 20；'y = 13； y =6所以，共有4種不同的支付方式.說明 當(dāng)方程的系數(shù)較小時，而且是求非負(fù)整數(shù)解或者是實際問題時，這時 候的解的組數(shù)往往較少，可以用整除的性質(zhì)加上枚舉，也能較容易地解出方程.多元一次不定方程可以化為二元一次不定方程.例6求方程9x+24y-5z=1000的整數(shù)解.解 設(shè)9x+24y=3t，即3x+8y=t，于是3t-5z=1000 .于是原方程可化為空十Sy = t,彳13t -5z =1000 用前面的方法可以求得的解為 = 3t-8uy = -t + 3u,u是整數(shù).的解為僱整數(shù).消去t，得(X 6000'Su + 15u,y = -2

14、000 + 3u - 5vP u(更是整數(shù).z = W004-3v,大約1500年以前，我國古代數(shù)學(xué)家張丘建在他編寫的張丘建算經(jīng)里， 曾經(jīng)提出并解決了“百錢買百雞”這個有名的數(shù)學(xué)問題，通俗地講就是下例.例7今有公雞每只五個錢，母雞每只三個錢，小雞每個錢三只用100個錢買100只雞，問公雞、母雞、小雞各買了多少只？解 設(shè)公雞、母雞、小雞各買x，y，z只，由題意列方程組玉+ 3y% 二 100,x + y + z = 100,化簡得15x+9y+z=300 .-得 14x+8y=200，即 7x+4y=100 .解 7x+4y=1得x=-ty=2于是7x+4y=100的一個特解為卜"00, £ = 200.由定理知7x+4y=100的所有整數(shù)解為t是整數(shù).j? = 400-F4t? y = 200-7t,由題意知，0vx, y, zv 100,所以0< 10Z4t