標(biāo)題: 初等數(shù)論入門(2)—最大公因數(shù)理論與一次不定方程 [打印本頁]

---

作者: 51hei小名    時間: 2016-6-20 22:06
標(biāo)題: 初等數(shù)論入門(2)—最大公因數(shù)理論與一次不定方程

    本節(jié)我們先來介紹最大公因數(shù)理論剩下的部分，然后再用最大公因數(shù)理論的觀點來看看一次不定方程。
    本節(jié)的主題是：最大公因數(shù)理論、一次不定方程。
   （注：這篇文章可以跟我很久以前寫的一篇文章銜接（注意：那篇文章有些不嚴(yán)謹(jǐn)）。有興趣的讀者可以去看那篇文章：一次不定方程的解法。本文將修改并引用其中一些內(nèi)容。）

    我們先來完整地闡述最大公因數(shù)理論（其實最小公倍數(shù)也屬于最大公因數(shù)理論）：

    定義5 如果存在一個d使d|q1,d|q2,…d|qk，那么我們稱d是q1,q2,…qk的公因數(shù)。如果這個d是所有公因數(shù)中最大的，那么我們稱這個d叫做q1,q2,…,qk的最大公因數(shù)，記作(q1,q2,…,qk)
    
    定義6 如果存在一個L使q1|L,q2|L,…,qk|L，那么我們稱d是q1,q2,…qk的公倍數(shù)。如果這個d是所有公倍數(shù)中最小的且是正的，那么我們稱這個L叫做q1,q2,…,qk的最小公倍數(shù)，記作[q1,q2,…,qk]
    

    定理2 最大公因數(shù)和最小公倍數(shù)具有如下性質(zhì)：
    1).q1,q2,q3,…,qk都整除c等價于[q1,q2,…,qk]|c。這是最小公倍數(shù)的本質(zhì)特征：公倍數(shù)一定是最小公倍數(shù)的倍數(shù)。
    2).D=(q1,q2,…)等價于D|q1,D|q2,……且對任給的滿足d|q1,d|q2……的d，都有d|D。這是最大公因數(shù)的本質(zhì)特征：公因數(shù)一定是最大公因數(shù)的因數(shù)。且如果一個數(shù)是公因數(shù)，而且它被其他的公因數(shù)整除，那么它是最大公因數(shù)。在上一節(jié)我們已經(jīng)證明了兩個數(shù)的情景。
    3).m(q1,q2,…)=(mq1,mq2,…)。就是說，一些數(shù)的最大公因數(shù)的倍數(shù)等于這些數(shù)的倍數(shù)的最大公因數(shù)。在上一節(jié)我們已經(jīng)證明了兩個數(shù)的情景。
    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。上一節(jié)里這個結(jié)論已經(jīng)證明了。
    6).(a,b)=1那么就有(a,bc)=(a,c)
    7).[a,b](a,b)=|ab|，這里|ab|表示ab的絕對值。如果我們限制a和b都是正整數(shù)，那么可以表述為：[a,b](a,b)=ab，即兩個正整數(shù)的最大公因數(shù)與他們的最小公倍數(shù)的乘積等于這兩個數(shù)的乘積。這里我們只考慮a,b是正整數(shù)的情形。這個結(jié)論上一節(jié)已證明。
    8).給定a,b，若記所有形如ax+by的數(shù)的集合為T，那么(a,b)=T中的最小正整數(shù)。上一節(jié)這個結(jié)論已經(jīng)證明了。
    9).8)可推廣為：給定q1,q2,q3,…,qk,那么(q1,q2,…,qk)=T中的最小正整數(shù)。這里T是所有形如q1x1+q2x2+…+qkxk的數(shù)的集合。上一節(jié)我們證明了兩個數(shù)的情景。
    10).一定存在x，y使(a,b)=ax+by

    我們來證明
    證(1)： 
    我們記[q1,q2,…,qk]=L，顯然如果L|c，那么qi|L可得qi|c。(i=1,2,…,k)
    現(xiàn)在只需證明如果q1|c,q2|c,…,qk|c，那么有L|c。設(shè)c=Lq+r (0≤r＜L)
    那么r=c-Lq，由于qi|L,qi|c得qi|r。(i=1,2,…,k)，那么得到r也是q1,q2,…,qk的公倍數(shù)。如果r>0就與L是最小公倍數(shù)矛盾。，因此r=0。所以c=Lq，即L|c。
 
    證(2)：顯然，如果能證明(4)，那么證明多個數(shù)的情形可以化歸為兩個數(shù)的情形，而這已經(jīng)被證明了（第二節(jié)引理8）。如果能證明(9)，那么這個結(jié)論可以被直接證明。
    第二節(jié)中，我們使用了較為高級的方法來證明引理8，現(xiàn)在我們給出幾種引理8的其他證法。
        引理8 如果s|a,s|b那么s|(a,b)。即兩個數(shù)的公因數(shù)一定是他們的最大公因數(shù)的因數(shù)。
        第2節(jié)中給出的證明：由引理7知可設(shè)(a,b)=ax+by，那么s|a,s|b可得s|ax+by=(a,b)。
        新的證法：設(shè)d=(a,b)，顯然s≤d。d|a,s|a可得[s,d]|a，d|b,s|b可得[s,d]|b，[s,d]也為a,b的公因數(shù)，故[s,d]≤d。由于最小公倍數(shù)[s,d]≥d，故[s,d]=d，這說明了s|d。
        用這種證法，可以直接證明(2)，這里不作詳細說明，有興趣的讀者可自行證明。
    
    證(3)：顯然，如果能證明(4)，那么證明多個數(shù)的情形可以化歸為兩個數(shù)的情形，而這已經(jīng)被證明了（第二節(jié)引理11）。
    稍加改進第2節(jié)引理11的方法，再結(jié)合我們證明的(2)，可以直接完成這個證明。但如果證明(9)，那么也可以用上一節(jié)的方法。
        設(shè)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)：我們只證明前者，而后者可以用類似的方法證明。(你可以試試。)
    設(shè)(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)：此結(jié)論于上一節(jié)已經(jīng)證明�，F(xiàn)照抄如下：
        引理9 如果(a,b)=1，且a|bc那么a|c。
        證：設(shè)ax+by=1，那么acx+bcy=c，由于a|acx，a|bcy故a|c
 
    證(6)：設(shè)D=(a,bc),d=(a,c)，d|a,d|c得d|bc,故d|D。D|a,D|bc，設(shè)(D,b)=r，r|b,r|D有r|a，則r|(a,b)=1,故r=1。由此得D|c，所以有D|d。所以D=d。 

    證(7)：上一節(jié)我們使用了算數(shù)基本定理來完成證明，這一節(jié)我們給出一個不依賴算數(shù)基本定理的直接證明。
    設(shè)(a,b)=d，a=Ad，b=Bd。對任給的滿足Ad|r,Bd|r的r,我們設(shè)r=mAd=nBd，則有mA=nB。A|nB推得A|n，同理B|m。再設(shè)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)：這個結(jié)論已經(jīng)在上一節(jié)證明了。設(shè)T中的最小正整數(shù)為d。對任意的n∈T，設(shè)n=dq+r。(0≤r＜d)。則r=n-dq，顯然r∈T。因為d是r中最小正整數(shù)，故r=0。由此得d|n。由于a,b∈T，故有d|a，d|b。則d|(a,b)。可設(shè)d=ax+by，則(a,b)|a,(a,b)|b得(a,b)|d。因此我們得到(a,b)=d。
     
    證(9)：由你來證明。 

    證(10)：由于d∈T，根據(jù)T的定義，這是顯然的。這啟示我們：方程ax+by=(a,b)總有整數(shù)解。
 
    好了，現(xiàn)在最大公因數(shù)理論的細節(jié)徹底跟你介紹完了，感謝你的耐心理解。讓我們看一個很有趣的問題： 

    我國古代有過一個著名的“百雞問題”：   

“今有雞翁一，值錢伍；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁、母、雛各幾何？”

 ——《張邱建算經(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)該如何解決呢？

    定義6 像這樣的，未知數(shù)個數(shù)多于方程個數(shù)，解受到某些限制(通常是整數(shù)解)的方程，我們稱作不定方程。（也叫丟番圖方程。）
    
    這一節(jié)，我們的第二件重要的事就是研究形如ax + by = c的一次不定方程。 
 
   引理15 一次不定方程ax + by = c 有整數(shù)解的充分必要條件（注：“充分必要條件”等價于“等價于”）為(a,b)|c。
    證：設(shè)(a,b)=d，如果整數(shù)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)都是整數(shù)。

    引理15也告訴了我們，要求Ax+By=c的解首先要求Ax+By=d的解。其中d=(A,B)。記A=ad,B=bd。此時方程兩邊同除以d，得到ax+by=1。此時(a,b)=1，而解并沒有變化。也就是說我們只要討論(a,b)=1的情況就可以了。因此，接下來我們總假設(shè)(a,b)=1。

    引理16(輾轉(zhuǎn)相除法) 如果 a = bq + r，那么(a,b)=(b,r)。
    證：設(shè)(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。 
    這是一種不需要分解素因數(shù)就可以求最大公因數(shù)的方法。稱作“輾轉(zhuǎn)相除法”或Euclid算法。
    
    我們之前建立的理論都只能說明一次不定方程是否可解，但是如何來求它的解呢？假設(shè)(a,b)=1，即如何將1表示為ax+by的形式？
    下面的引理回答了這個問題。

    引理17 若(a,b)=1,則ax+by=1必有解。并可以通過輾轉(zhuǎn)相除法求出一組解。
    證： 不妨假設(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)+r(n+1)
                由于b>r1>r2>r3>r4>r5>……>r(n+1)，余數(shù)是嚴(yán)格遞減的，所以經(jīng)過有限步驟后余數(shù)總會為0。不妨設(shè)r(n+1)=0，那么我們有：
                又由輾轉(zhuǎn)相除法得到(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的所有整數(shù)解為：x=X-bt,y=Y+at。t為整數(shù)。 
    證：帶入后顯然，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)，設(shè)x-r=bk,s-y=al，即k=l。所以r=x-bk=X-(k+t)b，s=y+ak=Y+(k+t)a。由于k+t是整數(shù)，因此這組解也是形如x=X-bt,y=Y+at的解。

     現(xiàn)在，我們有足夠的能力來解答《張丘建算經(jīng)》中的問題了，我們把這作為一個例題。

    例4 求出7x+4y=100的非負整數(shù)解。并完整解答張丘建算經(jīng)中的問題。
    解：由于(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的一組解。根據(jù)引理18，我們知道這個方程的所有解為：x=-100-4t,y=200+7t。 
    因此z=100-x-y=-3t，由于雞的數(shù)量必須是非負整數(shù)，我們有：
    

            -100 - 4t ≥0
             200 + 7t ≥0
                 - 3t ≥0 

        結(jié)合t也是整數(shù)，解得 -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}   

    怎么樣，數(shù)學(xué)的威力是不是很大？

 
    再給你來點練習(xí)題：

    1.證明：(a,b)=1,則(a+b,a^2-ab+b^2)=1或3.
    2.證明：若a不是完全平方數(shù)那么√a 一定不是有理數(shù)。
    3.證明：(a,b)=(a+b,[a,b])
    4.有1美分的硬幣，5美分的硬幣和25美分的硬幣一共10枚，它們一共恰好是1美元。問三種硬幣的數(shù)量？
    5.(附加題):五只猴子分桃子。結(jié)果發(fā)現(xiàn)無法均分，便不歡而散。當(dāng)天晚上，一猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第2只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第3只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第4只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。過了一會，第5只猴子悄悄前來，扔掉了一個桃子，拿走了自己的那份。最少有__________個桃子。

    呼，終于寫完這一節(jié)了，累死了，5個小時啊。。

    做出來把證明回復(fù)上來，我來幫你改作業(yè)。 

---

歡迎光臨 (http://www.torrancerestoration.com/bbs/)

Powered by Discuz! X3.1