本節我們先來介紹最大公因數理論剩下的部分，然后再用最大公因數理論的觀點來看看一次不定方程。
本節的主題是：最大公因數理論、一次不定方程。
（注：這篇文章可以跟我很久以前寫的一篇文章銜接（注意：那篇文章有些不嚴謹）。有興趣的讀者可以去看那篇文章：一次不定方程的解法。本文將修改并引用其中一些內容。）
我們先來完整地闡述最大公因數理論（其實最小公倍數也屬于最大公因數理論）：
定義5 如果存在一個d使d|q1,d|q2,…d|qk，那么我們稱d是q1,q2,…qk的公因數。如果這個d是所有公因數中最大的，那么我們稱這個d叫做q1,q2,…,qk的最大公因數，記作(q1,q2,…,qk)
定義6 如果存在一個L使q1|L,q2|L,…,qk|L，那么我們稱d是q1,q2,…qk的公倍數。如果這個d是所有公倍數中最小的且是正的，那么我們稱這個L叫做q1,q2,…,qk的最小公倍數，記作[q1,q2,…,qk]
定理2 最大公因數和最小公倍數具有如下性質：
1).q1,q2,q3,…,qk都整除c等價于[q1,q2,…,qk]|c。這是最小公倍數的本質特征：公倍數一定是最小公倍數的倍數。
2).D=(q1,q2,…)等價于D|q1,D|q2,……且對任給的滿足d|q1,d|q2……的d，都有d|D。這是最大公因數的本質特征：公因數一定是最大公因數的因數。且如果一個數是公因數，而且它被其他的公因數整除，那么它是最大公因數。在上一節我們已經證明了兩個數的情景。
3).m(q1,q2,…)=(mq1,mq2,…)。就是說，一些數的最大公因數的倍數等于這些數的倍數的最大公因數。在上一節我們已經證明了兩個數的情景。
4).(q1,q2,q3,…,qk)=((q1,q2),q3,…,qk)，且(q1,q2,…,qk)=((q1,q2,…,qr),(q(r+1),…,qk))
5).(a,b)=1，a|bc那么就有a|c。上一節里這個結論已經證明了。
6).(a,b)=1那么就有(a,bc)=(a,c)
7).[a,b](a,b)=|ab|，這里|ab|表示ab的絕對值。如果我們限制a和b都是正整數，那么可以表述為：[a,b](a,b)=ab，即兩個正整數的最大公因數與他們的最小公倍數的乘積等于這兩個數的乘積。這里我們只考慮a,b是正整數的情形。這個結論上一節已證明。
8).給定a,b，若記所有形如ax+by的數的集合為T，那么(a,b)=T中的最小正整數。上一節這個結論已經證明了。
9).8)可推廣為：給定q1,q2,q3,…,qk,那么(q1,q2,…,qk)=T中的最小正整數。這里T是所有形如q1x1+q2x2+…+qkxk的數的集合。上一節我們證明了兩個數的情景。
10).一定存在x，y使(a,b)=ax+by
我們來證明
證(1)：
我們記[q1,q2,…,qk]=L，顯然如果L|c，那么qi|L可得qi|c。(i=1,2,…,k)
現在只需證明如果q1|c,q2|c,…,qk|c，那么有L|c。設c=Lq+r (0≤r＜L)
那么r=c-Lq，由于qi|L,qi|c得qi|r。(i=1,2,…,k)，那么得到r也是q1,q2,…,qk的公倍數。如果r>0就與L是最小公倍數矛盾。，因此r=0。所以c=Lq，即L|c。
證(2)：顯然，如果能證明(4)，那么證明多個數的情形可以化歸為兩個數的情形，而這已經被證明了（第二節引理8）。如果能證明(9)，那么這個結論可以被直接證明。
第二節中，我們使用了較為高級的方法來證明引理8，現在我們給出幾種引理8的其他證法。
引理8 如果s|a,s|b那么s|(a,b)。即兩個數的公因數一定是他們的最大公因數的因數。 第2節中給出的證明：由引理7知可設(a,b)=ax+by，那么s|a,s|b可得s|ax+by=(a,b)。
新的證法：設d=(a,b)，顯然s≤d。d|a,s|a可得[s,d]|a，d|b,s|b可得[s,d]|b，[s,d]也為a,b的公因數，故[s,d]≤d。由于最小公倍數[s,d]≥d，故[s,d]=d，這說明了s|d。
用這種證法，可以直接證明(2)，這里不作詳細說明，有興趣的讀者可自行證明。
證(3)：顯然，如果能證明(4)，那么證明多個數的情形可以化歸為兩個數的情形，而這已經被證明了（第二節引理11）。
稍加改進第2節引理11的方法，再結合我們證明的(2)，可以直接完成這個證明。但如果證明(9)，那么也可以用上一節的方法。
設d=(q1,q2,…,qk)，D=(mq1,mq2,…,mqk)，我們來證明D=md。
d|q1,d|q2……可得md|mq1，md|mq2……故md|D。我們顯然有m|D。則有D/m|q1,D/m|q2……可得D/m|d。此即D|md。故D=md。
證(4)：我們只證明前者，而后者可以用類似的方法證明。(你可以試試。)
設(q1,q2,q3,…,qk)=D，(q1,q2)=d，(d,q3,…,qk)=P，要證明P=D。則P|d,d|q1,d|q2，得P|q1,P|q2。又由于P|qi(i=1,2,…,k)得到P|D。而D|qi(i=1,2,…,k)可得D|d,故D|P。因此D=P。
證(5)：此結論于上一節已經證明。現照抄如下：
引理9 如果(a,b)=1，且a|bc那么a|c。 證：設ax+by=1，那么acx+bcy=c，由于a|acx，a|bcy故a|c
證(6)：設D=(a,bc),d=(a,c)，d|a,d|c得d|bc,故d|D。D|a,D|bc，設(D,b)=r，r|b,r|D有r|a，則r|(a,b)=1,故r=1。由此得D|c，所以有D|d。所以D=d。
證(7)：上一節我們使用了算數基本定理來完成證明，這一節我們給出一個不依賴算數基本定理的直接證明。
設(a,b)=d，a=Ad，b=Bd。對任給的滿足Ad|r,Bd|r的r,我們設r=mAd=nBd，則有mA=nB。A|nB推得A|n，同理B|m。再設n=Ak,m=Bl，則ABk=ABl推得k=l。因此n=Ak,m=Bk。則r=ABdk，顯然有ABd|r。因此ABd=[Ad,Bd]。有[Ad,Bd]d=ABd^2，此即(a,b)[a,b]=ab。
證(8)：這個結論已經在上一節證明了。設T中的最小正整數為d。對任意的n∈T，設n=dq+r。(0≤r＜d)。則r=n-dq，顯然r∈T。因為d是r中最小正整數，故r=0。由此得d|n。由于a,b∈T，故有d|a，d|b。則d|(a,b)。可設d=ax+by，則(a,b)|a,(a,b)|b得(a,b)|d。因此我們得到(a,b)=d。
證(9)：由你來證明。
證(10)：由于d∈T，根據T的定義，這是顯然的。這啟示我們：方程ax+by=(a,b)總有整數解。
好了，現在最大公因數理論的細節徹底跟你介紹完了，感謝你的耐心理解。讓我們看一個很有趣的問題：
我國古代有過一個著名的“百雞問題”： “今有雞翁一，值錢伍；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁、母、雛各幾何？” ——《張邱建算經》 大概意思是說公雞五元一只，母雞三元一只，小雞一元三只，問100元如何買100只雞?
若設公雞x只，母雞y只，小雞z只，則有：
x+y+z=100
5x+3y+z/3=100
消去未知數z，得到 -14x -8y = -200,化簡后得 7x + 4y = 100
這個方程未知數個數多于方程數，而且要求整數解，而且還要是非負的。應該如何解決呢？
定義6 像這樣的，未知數個數多于方程個數，解受到某些限制(通常是整數解)的方程，我們稱作不定方程。（也叫丟番圖方程。）
這一節，我們的第二件重要的事就是研究形如ax + by = c的一次不定方程。
引理15 一次不定方程ax + by = c 有整數解的充分必要條件（注：“充分必要條件”等價于“等價于”）為(a,b)|c。
證：設(a,b)=d，如果整數x,y滿足方程ax+by=c，那么d|ax,d|by得d|c。
顯然，ax+by=d一定有解。若d|c，則可將方程兩邊同乘以c/d得到(xc/d)a+(yc/d)b=c，這里(xc/d)，(yc/d)都是整數。
引理15也告訴了我們，要求Ax+By=c的解首先要求Ax+By=d的解。其中d=(A,B)。記A=ad,B=bd。此時方程兩邊同除以d，得到ax+by=1。此時(a,b)=1，而解并沒有變化。也就是說我們只要討論(a,b)=1的情況就可以了。因此，接下來我們總假設(a,b)=1。
引理16(輾轉相除法) 如果 a = bq + r，那么(a,b)=(b,r)。
證：設(a,b)=d,(b,r)=D，r=a-bq，那么d|a,d|b推得d|r。因此d|D。D|b,D|r推得D|a。因此D|d。因此D=d。
這是一種不需要分解素因數就可以求最大公因數的方法。稱作“輾轉相除法”或Euclid算法。
我們之前建立的理論都只能說明一次不定方程是否可解，但是如何來求它的解呢？假設(a,b)=1，即如何將1表示為ax+by的形式？
下面的引理回答了這個問題。
引理17 若(a,b)=1,則ax+by=1必有解。并可以通過輾轉相除法求出一組解。
證： 不妨假設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)+r(n+1)
由于b>r1>r2>r3>r4>r5>……>r(n+1)，余數是嚴格遞減的，所以經過有限步驟后余數總會為0。不妨設r(n+1)=0，那么我們有：
又由輾轉相除法得到(a,b)=(b,r1)=(r1,r2)=(r2,r3)=……=(r(n),r(n+1))=（r(n),0)=r(n)，又由(a,b)=1,則r(n)=1.
改寫上面的式子：
r1 = a - b×q1
r2 = b - r1×q2
r3 = r1 - r2×q3
……
1 = r(n-2) - q(n)×r(n-1)
我們將r1帶入第二個式子，并保留ax+by的形式，然后再把r2帶入第三個式子……如此不停操作，最終我們能將1表示為ax+by的形式。
引理18 如果x=X和y=Y是ax+by=1的一組解，那么ax+by=1的所有整數解為：x=X-bt,y=Y+at。t為整數。
證：帶入后顯然，x=X-bt,y=Y+at是解。我們來證明所有解都形如此。
若還有一組解x=r,y=s滿足方程，那么ar+bs=1。我們有(x-r)a+(y-s)b=0，即(x-r)a=(s-y)b。由于(a,b)=1，則b|(x-r)，a|(s-y)，設x-r=bk,s-y=al，即k=l。所以r=x-bk=X-(k+t)b，s=y+ak=Y+(k+t)a。由于k+t是整數，因此這組解也是形如x=X-bt,y=Y+at的解。
現在，我們有足夠的能力來解答《張丘建算經》中的問題了，我們把這作為一個例題。
例4 求出7x+4y=100的非負整數解。并完整解答張丘建算經中的問題。
解：由于(7,4)=1，我們先解7x+4y=1.
7 = 4*1 + 3
4 = 3*1 + 1
所以 1 = 4 - 3 = 4 - (7 - 4) = 7*(-1) + 4*2
因此x=-1,y=2是7x+4y=1的一組解。兩邊同乘100，我們得到7*(-100)+4*(200)=100，因此x=-100,y=200是7x+4y=100的一組解。根據引理18，我們知道這個方程的所有解為：x=-100-4t,y=200+7t。
因此z=100-x-y=-3t，由于雞的數量必須是非負整數，我們有：
-100 - 4t ≥0
200 + 7t ≥0
- 3t ≥0
結合t也是整數，解得 -28 ≤t≤ -25，即 t = -25,-26,-27,-28.
于是我們得到這個問題的所有解答：
{x = 0, y = 25, z = 75}
{x = 4, y = 18, z = 78}
{x = 8, y = 11, z = 82}
{x = 12, y = 3, z = 85}
怎么樣，數學的威力是不是很大？
再給你來點練習題：
1.證明：(a,b)=1,則(a+b,a^2-ab+b^2)=1或3.
2.證明：若a不是完全平方數那么√a 一定不是有理數。
3.證明：(a,b)=(a+b,[a,b])
4.有1美分的硬幣，5美分的硬幣和25美分的硬幣一共10枚，它們一共恰好是1美元。問三種硬幣的數量？
5.(附加題):五只猴子分桃子。結果發現無法均分，便不歡而散。當天晚上，一猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第2只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第3只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第4只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第5只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。最少有__________個桃子。
呼，終于寫完這一節了，累死了，5個小時啊。。
做出來把證明回復上來，我來幫你改作業。 |
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
