第三节-最大公约数与最小公倍数

2020/9/121第三节最大公约数与最小公倍数一、最大公约数二、最小公倍数三、最大公约数与最小公倍数的性质2020/9/122一、最大公约数112,,(2),,,,nndadandaaa定义1.4若则称是的一个12(,,,).naaa公约数，其中最大的称为最大公约数，记作1212(,,,)=1,,,()nnaaaaaa若，则称互质素；12,,,naaa其中每两个都互质，则称两两互质.1212,,,,,,nnaaaaaa注：两两互质互质.由定义可以得到的两个结论：1212(1)(,,,)(,,,);nnaaaaaa(2)(,);baabb(0,);bb1.定义2020/9/123定理1.3.1若a=bq+c(a,b,cZ),则(a,b)=(b,c)证明：设d|a,d|b,则的d|bq.∵c=a-bq,∴d|c即有：a,b的公约数也是b,c的公约数.同理可证b,c的公约数也是a,b的公约数.这表明由a,b的全体公约数组成的集，与由b,c的全体公约数组成的集是同一个，故它们的最大公约数是同一个数，故(a,b)=(b,c).故结论成立2020/9/1242.辗转相除法定义：设有整数,(0)abb，ab在的带余数除法中，每次用余数去除除数，直到余数为0停止，这种运算方法称为辗转相除法。即有111,0abqrrb12221,0brqrrr211,0nnnnnnrrqrrr1111,0.nnnnnrrqrr(*)11()abqr余122()brqr余21()nnnnrrqr余111,(0)nnnnrrqr或2020/9/125定理1.3.2在上面的表达式(*)中，有：1(,),(0).nnabrr证明：(,),abd令,.dadb则111;rabqdr由1112221111nnnnnnnnabqrbrqrrrqrrrqr2122;rbrqdr由21.nnnnnrrrqdr由另一方面，111nnnnnrqrrr由,,nnrbra,.nrab即是的一个公约数1(,),(0).nnabrr所以，2020/9/126定理1.3.3若a,bN+，则一定存在整数s,tZ使得as+bt=(a,b).特别的有：推论1.3.4(a,b)=1的充要条件是：存在整数s,tZ使得as+bt=1.将其推广为k个的情形有：定理1.3.5若a1,a2,…,akN+，则一定存在整数m1,m2,…,mkZ使得a1m1+a2m2+…akmk=(a1,a2,…,ak).2020/9/127例1求下面各组数的最大公因数。(1)1859,1573;ab185915731286;15732865143;28614320.解：(2)138,36.ab18591573115732865143014322860(1859,1573)143.所以，(2)(138,36)6.注：亦可通过分解因数的方法求最大公因数.2020/9/128例2对于任意的整数n,求证：127148nn是既约的真分数.证明：∵14n+8=(12n+7)×1+2n+112n+7=(2n+1)×6+1故当nN+时，127148nn是既约分数.∴(14n+8,12n+7)=(12n+7,2n+1)=(2n+1,1)=12020/9/129定义1.5整数a1,a2,,an的公共倍数称为a1,a2,,an的公倍数。a1,a2,,an的正公倍数中的最小的一个叫做a1,a2,,an的最小公倍数，记为[a1,a2,,an].由定义1.5可知：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[a,b]=[b,a]；(ⅲ)[a1,a2,,ak]=[|a1|,|a2|,|ak|]；(ⅳ)若ab，则[a,b]=|b|.二、最小公倍数2020/9/1210定理1.3.6(a1,a2,…,ak)=D的充分必要条件是：(1)D|ai(i=1,2,…,k);(2)若d|ai,则d|D(i=1,2,…,k).证明（充分性证明）∵D|ai(i=1,2,…,k);∴D是a1,a2,…,ak的公约数，由定理1.1.1(8)和条件(2)知，对a1,a2,…,ak的任意公约数d，有dD，故有：(a1,a2,…,ak)=D（必要性证明）若(a1,a2,…,ak)=D，由公约数的定义知(1)成立；若d|ai(i=1,2,…,k)，由定理1.3.3的推论1可知，存在mi(i=1,2,…,k)使a1m1+a2m2+…akmk=(a1,a2,…,ak)，从而d|D，所以（2）成立三、最大公约数与最小公倍数的性质2020/9/1211定理1.3.7(a1,a2,…,ak)=d的充分必要条件是：12(,,,)1naaaddd定理1.3.8(a1,a2,…,ak)=d,且mZ+,c|ai(i=1,2,…,k),则有：1212(1)(,,,);(2)(,,,).nnmamamamdaaadcccc定理1.3.9[a1,a2,…,ak]=m的充分必要条件是：12(,,,)1nmmmaaa2020/9/1212定理1.3.10对任意的正整数a，b，有[,].(,)ababab证明：设m是a和b的一个公倍数，那么存在整数k1，k2，使得m=ak1，m=bk2，因此ak1=bk2.12.(,)(,)abkkabab于是11,,(,)(,)abababab令11(,)1.ab又1112akbk11bk11makabt(,)abtab1[,].(,)abtabab取时，即有(,)1,[,].ababab若则特别的2020/9/1213推论1两个整数的任何公倍数一定是最小公倍数的倍数.推论2设m，a，b是正整数，则[ma,mb]=m[a,b].3[138,36].例求1383613836[138,36]828.(138,36)64(,)6,[,]144,,.ababab例已知求1111111111116,6,(,)1.36(,)[,]6144241,24,3,8,aabbabababababababab解：记且又或或反过来.2020/9/1214定理1.3.1112122,,,(2)[,],naaanaam设为正整数，令2331[,],,[,]nnnmammam，12[,,,].nnaaam则注：把多个整数的公倍数化为两个数的公倍数来计算.1222331[,],[,],,[,]nnnaammammam证：由12,,,.nnmaaa知是的一个公倍数12,,,naaam对的任一公倍数，121222,[,]amamaammm由，且3.nmmmm，，，12[,,,].nnaaam推论若m是a1,a2,,an的公倍数，则[a1,a2,,an]m.2020/9/1215例5求（36,108,204）和[36,108,51].解：(36,108,204)=4×(9,27,51)=4×3×(3,9,17)=12×((3,9),17)=12×(3×(1,3),17)=12×(3,17)=12×1=12[36,108,204]=3×[12,36,17]=3×[[12,36],17]=3×[12×(1,3),17]=3×[36,17]=3×36×17=1836注：上述方法实际上是小学课本介绍的短除法.2020/9/1216定理1.3.12整数a1,a2,,an两两互素，即(ai,aj)=1，1i,jn，ij的充要条件是[a1,a2,,an]=a1a2an.例6设a，b，c是正整数，证明[a,b,c](ab,bc,ca)=abc。证：[a,b,c]=[[a,b],c]=[,].([,],)abcabc(ab,bc,ca)=(ab,(bc,ca))=(ab,c(a,b))([,],)([,],),[,][,][,]()abcabababcababcabababab代入即得证.2020/9/1217定理1.3.13如果a|bc，且(a,b)=1,则有：a|c.证明：∵a|bc，b|bc，∴bc是a,b的公倍数.∵(a,b)=1∴[a,b]=ab(定理1.3.12的推论）则有：ab|bc,∵b≠0∴a|c定理1.3.14若(a,b)=1,则有(a,bc)=(a,c).推论1若(a,bi)=1(i=1,2,…,k),则有(a,b1b2…bk)=1.推论2若(ai,bj)=1(i=1,2,…,n,j=1,2,…,n),则有:11(,)1.nnijijab2020/9/1218推论3若nN+,(a,b)=1,则有(an,bn)=1.定理1.3.15若a|c,b|c,(a,b)=1,则有ab|c.例7已知a2+b2=468,(a,b)+[a,b]=42,求a,b.例8求证：log25是无理数.例9设自然数A=10x+y(y是A的个位数字，x是非负整数)，则10n-1|(x+ny)(nN+).并用此法判断21498能否被19整除，21498能否被29整除.2020/9/1219内容小结1.最大公约数；3.最大公约数与最小公倍数的性质；作业P172(1),(3),(5);4;7;9;11;122.最小公倍数；