初中数学竞赛讲座-数论部分4(辗转相除法与最大公约数)

初中数学兴趣班系列讲座——数论部分唐一良数学工作室初中数学兴趣班系列讲座——数论部分唐一良数学工作室第四讲辗转相除法与最大公因数一、基础知识：a，bqa=bq+r（0≤r＜b）成立，且q，r是唯一的。证明：【存在性】作整数序列…，-3b，-2b，-b，0，b，2b，3b，…则a必在上述序列的某两项之间，即存在一个整数q使得qb≤a<(q+1)b成立。令a-qb=r，即证存在性。1 1 1 【唯一性】设q、r是满足a=bq+r，0≤r<b的另一对整数，因为bq+r=bq+r1 1 1 于是b(q-q)=r-r1 11 故b|q-q|=|r-r1 11rrbbq≠q11【说明】特别地，如果r=0，那么a=bq。这时，a被b整除，记作b|a，a，bb≠0q，ra=bq+r0≤r<|b|，这个事实称为带余除法定理，是整除理论的基础。最大公因数：若c|a，c|b，则称c是a，b的公因数。da，bda，bda，b记为：(a，b)=dd≥0时，da，ba，b1互素。记为：(a，b)=1辗转相除法：累次利用带余除法可以求出a，b相除法。又称欧几里得算法。例如，123456和7890的最大公因子是6，这可由下列步骤看出：abamodb12345678905106789051062784510627842322278423224622322462124621261260一般的，设a，b是任意两个正整数，由带余数除法，我们有下面的系列等式：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次带余数除法，总可以得到一个余数是零的等式，即rn1

=0(1)式所指出的计算方法，叫作辗转相除法。定理1：设a，b，c是任意三个不全为0的整数，且a=bq+c其中q是非零整数，则a，b与b，c有相同的公因数，因而（a，b）=（b，c）da，bdc=a-bqdb，c前一部分获证，第二部分随之得证。2是任意两个整数，则就是中最后一个不等于零的余数，即（a，b）=rn证明：由定理（1）即得r=(0，rn

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

，rn1

)=………=(r1

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

能够用辗转相除法直接算出，所以辗转相除法给出了求两整数的最大公因数的实际可行的算法。定理3：裴蜀定理（identity）得名于法国数学家艾蒂安·a，bdxy的线性丢番图方程（称为裴蜀等式：若a，b是整数，且a，，那么对于任意的整数，，aby一定是dx，yax+by=d成立。它的一个重要推论是：a，b互质的充要条件是存在整数x，y使ax+by=1.证明：⑴若b=0，则（a，b)=a.这时定理显然成立。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转证(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由倒数第三个式(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然后用同样的办法用它上面的等式逐个地消去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，它们给出了一个非负整数r＝au+bv这个r小于假定的最小的正整数Sr0S此时，a＝SqS|aS|b这样S是a和b的公因数，又a和b互素，那么S＝1推论(1)a，b的公因数与（a，b）的因数相同a，b是任意两个不全为零的整数，（ⅰ）若m是任意正整数，则（am，bm）=（a，b）m.（ⅱ）若的任一公因数，则（a

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

）=1， (a,b) (a,b)证明：当a，b有一为零时，定理显然成立，今设a，b都不为零.（ⅰ）易知a，b（am，bm（b=（a，bm，因此不妨假定a，b都是正数，在（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)故 （，）=当=（a，b）时，上式即为（a ，

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

）=d2

（d2

，a）=d3

，……（

，an1

）=dn

（*）于是我们有aa1

，……，an

n个整数，则（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

的一个d是aa1 2

an

d｜a1

a2

d，2同理，d｜d3

d｜dn

.因而d≤d≤dn

.故dn

aa1

，……，a的n最大公因数。二、典型例题例1任给的五个整数中，必有三个数之和被3整除.a

r(0

3,ii i i iri

0,1,2都出现，不妨设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至少有一个不出现，i则至少有三个ri

取相同的值，令rr1 2

rr(r或2)3a1+a2+a3=3(q1+q2+q3)+3r成立综合（1）（2）原题得证。例2从自然数1，2，3，…，1000中，最多可取出多少个数使得所取出的数中任意三个数之和能被18整除？解：设a，b，c，d是所取出的数中的任意4个数，则m，n是自然数。于是c-d=18（m-n）。21818a=18a+r，b=18b

+r，a，b，c1 1 1

1 1 1是整数。于是a+b+c=18（a+b+c）+3r。1 1 1因为1| a+b+所以18|即6推知=61因为1000=5518+1，1，2，…，10006，24，42，…，99656318整除。3求证：如果ab是整数，那么a，b，a2b2，a2b25整除。a,b5整除，则命题获证。若a,b之中任何一个都不能被5整除，则a,b只能形如5m1,5m2，由于(5m1)225m210m15(5m22m)1(5m2)225m220m45(5m24m)4于是，a2,b2形如5m1,5m4a2,b2一个形如5m1，另一个形如5m4a2+b25a2,b2同为5m1形或5m4a2-b25整除；a，ba2b2a2b25整除。例4正整数a,a, ,a 的和为1001，(a,a, ,

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

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

a 10d，10从而，有d1001<101,由此可见，d至多取值7139110由于1001可以写成10个数的和：9191

91+18210个其中每个数都能被91整除，所以d的最大值为91。5a93,4,56x3y3a无整数解。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，应联想到先证明

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中的一个，故得证。】由m>nFn

|(Fm

2)xFm

2xFn即FxF

2，设d=(F,Fn m

)，由Fm

xFn

2，推出d|2，所以d=1或2，Fd=1，即(FFn

)=1.例7设ax

ax+by（a,b0）的整数中最小的正数，试证：对于任意整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均为整数，故r是一个比ax+by还要小的形如ax+by的正整数，0 0 0 0ax+byr=0ax

|ax+by0 0 0 0三、模拟训练1.求（1056,3960）121056396025281980226499031324951144165415所以（1056,3960）=23311解法2：分解质因数法：1056=233114,3960=2331115所以（1056,3960）=23311=264解法（辗转相除法：（1）105639603960=10563+792（2）79210561056=7921+264264792792=26426410563960的最大公约数。a,b,c为正整数，证明：((a,b),c)=(a,b,c)分析：((a,b),c)指的是a和b的最大公约数与c的最大公约数，要证明((a,b),c)=(a,b,c)，只需证明(a,b,c)|((a,b),c)，并且((a,b),c)|(a,b,c)所以(a,b,c)|(a,b)又因为(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，试证：分数14n

不能约简分析：要证明这个分数不可约，只需证明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

不能约简已知两个正整数之和为104055，它们的最大公约数是6937x,y，依题意得xy104055 ①(x,y)6937 ②x6937ay6937b，且(ab1，代入①得ab15由于(ab)14种可能：a1 a2 a4 a7 ， ， ，b14 b13 b11 b8分别代入的表达式，得x6937 x13874 x27748 x48559 ； ；