初中數(shù)學(xué)競(jìng)賽講座-數(shù)論部分4(輾轉(zhuǎn)相除法與最大公約數(shù))

初中數(shù)學(xué)興趣班系列講座——數(shù)論部分唐一良數(shù)學(xué)工作室初中數(shù)學(xué)興趣班系列講座——數(shù)論部分唐一良數(shù)學(xué)工作室第四講輾轉(zhuǎn)相除法與最大公因數(shù)一、基礎(chǔ)知識(shí)：a，bqa=bq+r（0≤r＜b）成立，且q，r是唯一的。證明：【存在性】作整數(shù)序列…，-3b，-2b，-b，0，b，2b，3b，…則a必在上述序列的某兩項(xiàng)之間，即存在一個(gè)整數(shù)q使得qb≤a<(q+1)b成立。令a-qb=r，即證存在性。1 1 1 【唯一性】設(shè)q、r是滿足a=bq+r，0≤r<b的另一對(duì)整數(shù)，因?yàn)閎q+r=bq+r1 1 1 于是b(q-q)=r-r1 11 故b|q-q|=|r-r1 11rrbbq≠q11【說(shuō)明】特別地，如果r=0，那么a=bq。這時(shí)，a被b整除，記作b|a，a，bb≠0q，ra=bq+r0≤r<|b|，這個(gè)事實(shí)稱為帶余除法定理，是整除理論的基礎(chǔ)。最大公因數(shù)：若c|a，c|b，則稱c是a，b的公因數(shù)。da，bda，bda，b記為：(a，b)=dd≥0時(shí)，da，ba，b1互素。記為：(a，b)=1輾轉(zhuǎn)相除法：累次利用帶余除法可以求出a，b相除法。又稱歐幾里得算法。例如，123456和7890的最大公因子是6，這可由下列步驟看出：abamodb12345678905106789051062784510627842322278423224622322462124621261260一般的，設(shè)a，b是任意兩個(gè)正整數(shù)，由帶余數(shù)除法，我們有下面的系列等式：a=bq

r，0<

<b，1 1 1b=r1

q+r2

，0<r2

<r，1……………rn2

=rn1

q+rn

，0<rn

<rn1

， (1)r =rn1

qn1

+rn1

，r =0n1bb次帶余數(shù)除法，總可以得到一個(gè)余數(shù)是零的等式，即rn1

=0(1)式所指出的計(jì)算方法，叫作輾轉(zhuǎn)相除法。定理1：設(shè)a，b，c是任意三個(gè)不全為0的整數(shù)，且a=bq+c其中q是非零整數(shù)，則a，b與b，c有相同的公因數(shù)，因而（a，b）=（b，c）da，bdc=a-bqdb，c前一部分獲證，第二部分隨之得證。2是任意兩個(gè)整數(shù)，則就是中最后一個(gè)不等于零的余數(shù)，即（a，b）=rn證明：由定理（1）即得r=(0，rn

)=(r ，r)n1 n=(rn

，rn1

)=………=(r1

，b)=(a，b) 證完rn

能夠用輾轉(zhuǎn)相除法直接算出，所以輾轉(zhuǎn)相除法給出了求兩整數(shù)的最大公因數(shù)的實(shí)際可行的算法。定理3：裴蜀定理（identity）得名于法國(guó)數(shù)學(xué)家艾蒂安·a，bdxy的線性丟番圖方程（稱為裴蜀等式：若a，b是整數(shù)，且a，，那么對(duì)于任意的整數(shù)，，aby一定是dx，yax+by=d成立。它的一個(gè)重要推論是：a，b互質(zhì)的充要條件是存在整數(shù)x，y使ax+by=1.證明：⑴若b=0，則（a，b)=a.這時(shí)定理顯然成立。1 1 1 a，b0，∵(a，b)=(a，-b)b，(a，b)=dax+by=dd(a)x+(b)y=1(a，b)=11 1 1 1轉(zhuǎn)證(a1

)y=1。由帶余除法：1a=(q)b+(r

)0r<b1 1 1 1 1 1b=(q)(r

)+(r)0r<r1 221(r)=(q21

1 2)(r)+(r

)0r<r1 3 2 3 3 2.....(r )=(q )(r )+(r )n-3 n-1 n-2 n-1(r )=(q)(r )+(r)n-2 n n-1 n(r )=(q )(r)n-1 n+1 n于是，(a，b)=(b，r，r)=...=(r ，r)=11 1 1 1 1 2 n-1 n故(r )=(q)(r )+1，即1=(r )-(q)(r )n-2 n n-1 n-2 n n-1由倒數(shù)第三個(gè)式(r )=(r )-(q )(r )代入上式，得n-1 n-3 n-1 n-21=[1+(q)(q )](r )-(q)(r )n n-1 n-2 n n-3然后用同樣的辦法用它上面的等式逐個(gè)地消去r ，...r，n-2 11 可證得1=(a)x+(b)y1 （必要性）uvau+bvS＝1Sabqr0≤r＝a-sq＝a-(au+bv)q＝a(1-uq)+b(-vq)＜S即存在u＝1-uq和v＝-vq，它們給出了一個(gè)非負(fù)整數(shù)r＝au+bv這個(gè)r小于假定的最小的正整數(shù)Sr0S此時(shí)，a＝SqS|aS|b這樣S是a和b的公因數(shù)，又a和b互素，那么S＝1推論(1)a，b的公因數(shù)與（a，b）的因數(shù)相同a，b是任意兩個(gè)不全為零的整數(shù)，（?。┤鬽是任意正整數(shù)，則（am，bm）=（a，b）m.（ⅱ）若的任一公因數(shù)，則（a

(a,b) a b，特別（ ，

）=1， (a,b) (a,b)證明：當(dāng)a，b有一為零時(shí)，定理顯然成立，今設(shè)a，b都不為零.（?。┮字猘，b（am，bm（b=（a，bm，因此不妨假定a，b都是正數(shù)，在（1）里，把各式兩邊同乘以m，即得am=(bm) q+r1 1

m，0<r1

m<bm，bm=(r1

m) q+r2

m，0<r2

m<rm，1……………rn1

m=（rn

.n12得（am，bm）rn（ⅱ）由（ⅰ）1，

m=(a，b)m，因而（?。┇@證.a b（，

a） =（b

b，

）（a，b（b，a b (a,b)故 （，）=當(dāng)=（a，b）時(shí)，上式即為（a ，

）=1 證完(a,b) (a,b)又若（aa1

）=d2

（d2

，a）=d3

，……（

，an1

）=dn

（*）于是我們有aa1

，……，an

n個(gè)整數(shù)，則（aa1 2

，……，an

）=dn證明：由，d｜an n

，d｜n

n1

，但d

n1

｜dn2

，故dn

｜a ，dn1

｜dn2

，由此類推，最后得到d｜an n

，d｜n

n1

，……，dn

｜a，即d1

aa1

，……，an

的一個(gè)d是aa1 2

an

d｜a1

a2

d，2同理，d｜d3

d｜dn

.因而d≤d≤dn

.故dn

aa1

，……，a的n最大公因數(shù)。二、典型例題例1任給的五個(gè)整數(shù)中，必有三個(gè)數(shù)之和被3整除.a

r(0

3,ii i i iri

0,1,2都出現(xiàn)，不妨設(shè)r1

0,r2

r3

2，a a a q q 則+ + =3( + + )+3成立a a a q q 1 2 3 1 2 3r0,1,2至少有一個(gè)不出現(xiàn)，i則至少有三個(gè)ri

取相同的值，令rr1 2

rr(r或2)3a1+a2+a3=3(q1+q2+q3)+3r成立綜合（1）（2）原題得證。例2從自然數(shù)1，2，3，…，1000中，最多可取出多少個(gè)數(shù)使得所取出的數(shù)中任意三個(gè)數(shù)之和能被18整除？解：設(shè)a，b，c，d是所取出的數(shù)中的任意4個(gè)數(shù)，則m，n是自然數(shù)。于是c-d=18（m-n）。21818a=18a+r，b=18b

+r，a，b，c1 1 1

1 1 1是整數(shù)。于是a+b+c=18（a+b+c）+3r。1 1 1因?yàn)?| a+b+所以18|即6推知=61因?yàn)?000=5518+1，1，2，…，10006，24，42，…，99656318整除。3求證：如果ab是整數(shù)，那么a，b，a2b2，a2b25整除。a,b5整除，則命題獲證。若a,b之中任何一個(gè)都不能被5整除，則a,b只能形如5m1,5m2，由于(5m1)225m210m15(5m22m)1(5m2)225m220m45(5m24m)4于是，a2,b2形如5m1,5m4a2,b2一個(gè)形如5m1，另一個(gè)形如5m4a2+b25a2,b2同為5m1形或5m4a2-b25整除；a，ba2b2a2b25整除。例4正整數(shù)a,a, ,a 的和為1001，(a,a, ,

)d，求d的最大值。1 2 10 1 2 10解：因d是a,a, ,a 的最大公約數(shù)，故d|1001，即d是1001=71113的約數(shù)，又1 2 10kd|ak

,10),可得ad，所以k1001=aa1 2

a 10d，10從而，有d1001<101,由此可見(jiàn)，d至多取值7139110由于1001可以寫(xiě)成10個(gè)數(shù)的和：9191

91+18210個(gè)其中每個(gè)數(shù)都能被91整除，所以d的最大值為91。5a93,4,56x3y3a無(wú)整數(shù)解。x,y,1 1 2 2 1 記x=3q+r，y=3q+r(0r,r1 1 2 2 1 1 1 1 1 2 2 2 則x3=(3q+r)3=9Q+R,y3=(3q+r)3=9Q+1 1 1 1 2 2 2 R 其中 和 被9R 1 2分別與r3和r391 2

=0,1R1R

=0,1或821 2 1 2 1 x3+y3=9(Q+Q)+R+RR+R90,1,2,78，x3+y31 2 1 2 1 6Fk

22k1,k0（）證明：若>n，則Fn

|(Fm

2)（2）mn，則(F

)1m n（1）分析題目所證的式子為

1|2

1，應(yīng)聯(lián)想到先證明

1|22m1再利用

12

)(22n

1)，證明原命題證明首先將xkyk分解因式，即xkyk=(xy)(xk1xk2y在上式中，取x22n1，==2n-，得

xyk2yk)得到

2m1|22m

121

(xkxk2y xyk2yk1)又

12

)(22n

)，故可得

1|22m1【另證：

1(22m

)(22m

)(22m

1)

(20

)(20

1)m>n≥0，故n必為m-1,m-2,…,0中的一個(gè)，故得證?！坑蒻>nFn

|(Fm

2)xFm

2xFn即FxF

2，設(shè)d=(F,Fn m

)，由Fm

xFn

2，推出d|2，所以d=1或2，F(xiàn)d=1，即(FFn

)=1.例7設(shè)ax

ax+by（a,b0）的整數(shù)中最小的正數(shù)，試證：對(duì)于任意整0 0x,yax

|ax+by0 0x,yax+by

+byr<

+byr00<r<

+by

0 0 0 0q)+b(y-yq)0 0 0 0而x-xq與y-yq均為整數(shù)，故r是一個(gè)比ax+by還要小的形如ax+by的正整數(shù)，0 0 0 0ax+byr=0ax

|ax+by0 0 0 0三、模擬訓(xùn)練1.求（1056,3960）121056396025281980226499031324951144165415所以（1056,3960）=23311解法2：分解質(zhì)因數(shù)法：1056=233114,3960=2331115所以（1056,3960）=23311=264解法（輾轉(zhuǎn)相除法：（1）105639603960=10563+792（2）79210561056=7921+264264792792=26426410563960的最大公約數(shù)。a,b,c為正整數(shù)，證明：((a,b),c)=(a,b,c)分析：((a,b),c)指的是a和b的最大公約數(shù)與c的最大公約數(shù)，要證明((a,b),c)=(a,b,c)，只需證明(a,b,c)|((a,b),c)，并且((a,b),c)|(a,b,c)所以(a,b,c)|(a,b)又因?yàn)?a,b,c)|c，所以(a,b,c)|((a,b),c)反之，((a,b),c)|(a,b)，((a,b),c)|c所以((a,b),c)|a，((a,b),c)|b，所以((a,b),c)|(a,b,c)所以((a,b),c)=(a,b,c)

4n，試證：分?jǐn)?shù)14n

不能約簡(jiǎn)分析：要證明這個(gè)分?jǐn)?shù)不可約，只需證明21n+414n+31證明：(21n+4,14n+3)=(21n+4-14n-3,14n+3)=(7n+1,14n+3)=(7n+1,14n+3-14n-2)=(7n+1,1)=14n14n

不能約簡(jiǎn)已知兩個(gè)正整數(shù)之和為104055，它們的最大公約數(shù)是6937x,y，依題意得xy104055 ①(x,y)6937 ②x6937ay6937b，且(ab1，代入①得ab15由于(ab)14種可能：a1 a2 a4 a7 ， ， ，b14 b13 b11 b8分別代入的表達(dá)式，得x6937 x13874 x27748 x48559 ； ；