初等数论教案 第二节 最大公因数与辗转相除法

第二节最大公因数与辗转相除法第三节最小公倍数教学目的：1、掌握最大公因数与最小公倍数性质；2、掌握辗转相除法；3、会求最大公因数与最小公倍数.教学重点：最大公因数与最小公倍数性质教学难点：辗转相除法教学课时：6课时教学过程一、最大公因数1、定义1整数a1,a2,,ak的公共约数称为a1,a2,,ak的公约数.不全为零的整数a1,a2,,ak的公约数中最大的一个叫做a1,a2,,ak的最大公约数（或最大公因数），记为(a1,a2,,ak).注：1、由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数.2、如果(a1,a2,,ak)=1，则称a1,a2,,ak是互素的（或互质的）；如果(ai,aj)=1，1i,jk，ij，则称a1,a2,,ak是两两互素的（或两两互质的）.显然，a1,a2,,ak两两互素可以推出(a1,a2,,ak)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2.2、定理1下面的等式成立：(ⅰ)(a1,a2,,ak)=(|a1|,|a2|,,|ak|)；(ⅱ)(a,1)=1，(a,0)=|a|，(a,a)=|a|；(ⅲ)(a,b)=(b,a)；(ⅳ)若p是素数，a是整数，则(p,a)=1或pa；(ⅴ)若a=bqr，则(a,b)=(b,r).证明：(ⅰ)(ⅳ)留作习题.(ⅴ)由第一节定理1可知，如果da，db，则有dr=abq，反之，若db，dr，则da=bqr.因此a与b的全体公约数的集合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相等，即(a,b)=(b,r).证毕3、定理2设a1,a2,,akZ，记A={y；y=，xiZ，ik}.如果y0是集合A中最小的正数，则y0=(a1,a2,,ak).证明设d是a1,a2,,ak的一个公约数，则dy0，所以dy0.另一方面，由第一节例2知，y0也是a1,a2,,ak的公约数.因此y0是a1,a2,,ak的公约数中的最大者，即y0=(a1,a2,,ak).证毕推论1设d是a1,a2,,ak的一个公约数，则d(a1,a2,,ak).注：这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数.推论2(ma1,ma2,,mak)=|m|(a1,a2,,ak).推论3记=(a1,a2,,ak)，则=1，特别地,=1.4、定理3(a1,a2,,ak)=1的充要条件是存在整数x1,x2,,xk，使得a1x1a2x2akxk=1.证明必要性由定理2得到.充分性若式(1)成立，如果(a1,a2,,ak)=d>1，那么由dai（1ik）推出da1x1a2x2akxk=1，这是不可能的.所以有(a1,a2,,ak)5、定理4对于任意的整数a，b，c，下面的结论成立：(ⅰ)由bac及(a,b)=1可以推出bc；(ⅱ)由bc，ac及(a,b)=1可以推出abc.证明(ⅰ)若(a,b)=1，由定理2，存在整数x与y，使得axby=1.因此acxbcy=c.(2)由上式及bac得到bc.结论(ⅰ)得证；(ⅱ)若(a,b)=1，则存在整数x，y使得式(2)成立.由bc与ac得到abac，abbc，再由式(2)得到abc.结论(ⅱ)得证.证毕推论1若(a,b)=1，则(a,bc)=(a,c).证明设d是a与bc的一个公约数，则da，dbc，由式（2）得到，d|c,即d是a与c的公约数.另一方面，若d是a与c的公约数，则它也是a与bc的公约数.因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a,bc)=(a,c).证毕推论2若(a,bi)=1，1in，则(a,b1b2bn)=1.证明留作习题.6、定理5对于任意的n个整数a1,a2,,an，记(a1,a2)=d2，(d2,a3)=d3，，(dn2,an1)=dn1，(dn1,an)=dn，则dn=(a1,a2,,an).证明由定理2的推论，我们有dn=(dn1,an)dnan，dndn1，dn1=(dn2,an1)dn1an1，dn1dn2，dnan，dnan1，dndn2，dn2=(dn3,an2)dn2an2，dn2dn3dnan，dnan1，dnan2，dndn3，d2=(a1,a2)dnan，dnan1，，dna2，dna1，即dn是a1,a2,,an的一个公约数.另一方面，对于a1,a2,,an的任何公约数d，由定理2的推论及d2,,dn的定义，依次得出da1，da2dd2，dd2，da3dd3，ddn1，danddn，因此dn是a1,a2,,an的公约数中的最大者，即dn=(a1,a2,,an).例1证明：若n是正整数，则是既约分数.解：由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1.注：一般地，若(x,y)=1，那么，对于任意的整数a，b，有(x,y)=(xay,y)=(xay,yb(xay))=(xay,(ab1)ybx)，因此，是既约分数.例2证明：121n22n12，nZ.解：由于121=112，n22n12=(n1)211，所以，若112(n1)211，(3)则11(n1)2，因此，由定理4的推论1得到11n1，112(n1)2.再由式(3)得到11211，这是不可能的.所以式(3)不能成立.注：这个例题的一般形式是：设p是素数，a，b是整数，则pk(anb)kpk1c，其中c是不被p整除的任意整数，k是任意的大于1的整数.例3设a，b是整数，且9a2abb2，则3(a,b).解：由式(4)得到9(ab)23ab3(ab)23ab3(ab)23ab(59(ab)2.再由式(4)得到93ab3ab.因此，由定理4的推论1，得到3a或3b若3a，由式(5)得到3b；若3b，由(5)式也得到3a.因此，总有3由定理2的推论推出3(a,b).例4设a和b是正整数，b>2，则2b12a1.解：(ⅰ)若a<b，且2b12a1.(6成立，则2b12a12b2a22a(2ba1)于是a=1，ba=1，即b=2，这是不可能的，所以式(6)不成立.(ⅱ)若a=b，且式(6)成立，则由式(6)得到2a1(2a1)22a122a122a于是b=a=1，这是不可能的，所以式(6)不成立.(ⅲ)若a>b，记a=kbr，0r<b，此时2kb1=(2b1)(2(k1)b2(k2)b1)=(2b1)Q，其中Q是整数.所以2a1=2kb+r1=2r(2kb11)=2r((2b1)Q1)1=(2b1)Q(2r1)，其中Q是整数.因此2b12a12b12r1在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立.综上证得2b12a1.二、最小公倍数1、定义1整数a1,a2,,ak的公共倍数称为a1,a2,,ak的公倍数.a1,a2,,ak的正公倍数中的最小的一个叫做a1,a2,,ak的最小公倍数，记为[a1,a2,,ak].2、定理1下面的等式成立：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[a,b]=[b,a]；(ⅲ)[a1,a2,,ak]=[|a1|,|a2|,|ak|]；(ⅳ)若ab，则[a,b]=|b|.证明留作习题.由定理1中的结论(ⅲ)可知，在讨论a1,a2,,ak的最小公倍数时，不妨假定它们都是正整数.在本节中总是维持这一假定.最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理.3、定理2对任意的正整数a，b，有[a,b]=.证明：设m是a和b的一个公倍数，那么存在整数k1，k2，使得m=ak1，m=bk2，因此ak1=bk2.(1)于是.由于=1，所以，其中t是某个整数.将上式代入式(1)得到m=t.(2)另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数.当t=1时，得到最小公倍数[a,b]=.推论1两个整数的任何公倍数可以被它们的最小公倍数整除.证明由式(2)可得证.这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数.推论2设m，a，b是正整数，则[ma,mb]=m[a,b].证明由定理2及前面的定理2的推论得到[ma,mb]==m[a,b].证毕4、定理3对于任意的n个整数a1,a2,,an，记[a1,a2]=m2，[m2,a3]=m3，，[mn2,an1]=mn1，[mn1,an]=mn，则[a1,a2,,an]=mn.证明：我们有mn=[mn1,an]mn1mn，anmn，mn1=[mn2,an1]mn2mn1mn，anmn，an1mn1mn，mn2=[mn3,an2]mn3mn2mn，anmn，an1mn，an2mn，m2=[a1,a2]anmn，，a2mn，a1mn，即mn是a1,a2,,an的一个公倍数.另一方面，对于a1,a2,,an的任何公倍数m，由定理2的推论及m2,,mn的定义，得m2m，m3m，，mn即mn是a1,a2,,an最小的正的公倍数.证毕推论若m是整数a1,a2,,an的公倍数，则[a1,a2,,an]m.证明：留作习题.定理4整数a1,a2,,an两两互素，即(ai,aj)=1，1i,jn，ij的充要条件是[a1,a2,,an]=a1a2an.证明：必要性因为(a1,a2)=1，由定理2得到[a1,a2]==a1a2.由(a1,a3)=(a2,a3)=1及前面的定理4推论得到(a1a2,a3由此及定理3得到[a1,a2,a3]=[[a1,a2],a3]=[a1a2,a3]=a1a如此继续下去，就得到式(3).充分性用归纳法证明.当n=2时，式(3)成为[a1,a2]=a1a2.a1a2=[a1,a2]=(a1,a2)=1，即当n=2时，充分性成立.假设充分性当n=k时成立，即[a1,a2,,ak]=a1a2ak(ai,aj)=1，1i,jk，ij对于整数a1,a2,,ak,ak+1，使用定理3中的记号，由定理3可知[a1,a2,,ak,ak+1]=[mk,ak+1].(4)其中mk=[a1,a2,,ak].因此，如果[a1,a2,,ak,ak+1]=a1a2akak+1那么，由此及式(4)得到[a1,a2,,ak,ak+1]=[mk,ak+1]==a1a2akak+1，即=a1a2ak，显然mka1a2ak，(mk,ak+1)1.(mk,ak+1)=1，(5)并且mk=a1a2ak.由式(6)与式(5)推出(ai,ak+1)=1，1ik；(7)由式(6)及归纳假设推出(ai,aj)=1，1i,jk，ij.(8)综合式(7)与式(8)，可知当n=k1时，充分性成立.由归纳法证明了充分性.证毕定理4有许多应用.例如，如果m1,m2,,mk是两两互素的整数，那么，要证明m=m1m2mk整除某个整数Q，只需证明对于每个i，1ik，都有miQ.这一点在实际计算中是很有用的.对于函数f(x)，要验证命题“mf(n)，nZ”是否成立，可以用第二节例5中的方法，验证“mf(r)，r=0,1,,m1”是否成立.这需要做m次除法.但是，若分别验证“mif(ri)，ri=0,1,,mi1，1ik”是否成立，则总共需要做m1m2例1设a，b，c是正整数，证明：[a,b,c](ab,bc,ca)=abc.解：由定理3和定理2有[a,b,c]=[[a,b],c]=，(9)由第三节定理5和定理2的推论，(ab,bc,ca)=(ab,(bc,ca))=(ab,c(a,b))=.(10)联合式(9)与式(10)得到所需结论.例2对于任意的整数a1,a2,,an及整数k，1kn，证明：[a1,a2,,an]=[[a1,,ak],[ak+1,,an]].解：因为[a1,a2,,an]是a1,,ak,ak+1,,an的公倍数，所以由定理2推论，推出[a1,,ak][a1,a2,,an]，[ak+1,,an][a1,a2,,an]，再由定理3推论知[[a1,,ak],[ak+1,,an]][a1,a2,,an].(11)另一方面，对于任意的ai（1in），显然ai[[a1,,ak],[ak+1,,an]]，所以由定理3推论可知[a1,a2,,an][[a1,,ak],[ak+1,,an]]，联合上式与式(11)得证.例3设a，b，c是正整数，证明：[a,b,c][ab,bc,ca]=[a,b][b,c][c,a].解：由定理2推论2及例2，有[a,b,c][ab,bc,ca]=[[a,b,c]ab,[a,b,c]bc,[a,b,c]ca]=[[a2b,ab2,abc],[abc,b2c,bc2],[a2c,abc,ac=[a2b,ab2,abc,abc,b2c,bc2,a2c,abc,ac=[abc,a2b,a2c,b2c,b2a,c2a,以及[a,b][b,c][c,a]=[[a,b]b,[a,b]c][c,a]=[ab,b2,ac,bc][c,a]=[ab[c,a],b2[c,a],ac[c,a],bc[c,a]]=[abc,a2b,b2c,b2a,ac2,a2c,bc2,=[abc,a2b,a2c,b2c,b2a,c2a,c由此得证.三、辗转相除法本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法.它是数论中的一个重要方法，在其他数学分支中也有广泛的应用.1、定义1下面的一组带余数除法，称为辗转相除法.设a和b是整数，b0，依次做带余数除法：a=bq1r1，0<r1<|b|，b=r1q2r2，0<r2<r1，rk1=rkqk+1rk+1，0<rk+1<rk，(1)rn2=rn1qnrn，0<rn<rn-1，rn1=rnqn+1.由于b是固定的，而且|b|>r1>r2>，所以式(1)中只包含有限个等式.下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计.2、引理1用下面的方式定义Fibonacci数列{Fn}：F1=F2=1，Fn=Fn1Fn2，n3，那么对于任意的整数n3，有Fn>n2，(2)其中=.证明：容易验证2=1.当n=3时，由F3=2>=可知式(2)成立.假设式(2)对于所有的整数kn（n3）成立，即Fk>k2，kn，则Fn+1=FnFn1>n2n3=n3(1)=n32=n1，即当k=n1时式(2)也成立.由归纳法知式(2)对一切n3成立.证毕.3、定理1(Lame)设a,bN，a>b，使用在式(1)中的记号，则n<5log10b.证明：在式(1)中，rn1，qn+12，qi1（1in），因此rn1=F2，rn12rn2=F3，rn2rn1rnF3F2=F4br1r2Fn+1Fn=Fn+2，由此及式(2)得bn=，即log10bnlog10，这就是定理结论.证毕4、定理2使用式(1)中的记号，记P0=1，P1=q1，Pk=qkPk1Pk2，k2，Q0=0，Q1=1，Qk=qkQk1Qk2，k2，则aQkbPk=(1)k1rk，k=1,2,,n.(3)证明：当k=1时，式(3)成立.当k=2时，有Q2=q2Q1Q0=q2，P2=q2P1P0=q2q11，此时由式(1)得到aQ2bP2=aq2b(q2q11)=(abq1)q2b=r1q2b=r2，即式(3)成立.假设对于k<m（1mn）式aQmbPm=a(qmQm1Qm2)b(qmPm1Pm2)=(aQm1bPm1)qm(aQm2bPm2)=(1)m2rm1qm(1)m3rm2=(1)m1(rm2rm1qm)=(1)m1rm，即式(3)当k=m时也成立.定理由归纳法得证.证毕5、定理3使用式(1)中的记号，有rn=(a,b).证明：由第三节定理1，从式(1)可见rn=(rn1,rn)=(rn2,rn1)==(r1,r2)=(b,r1)=(a,b).证毕.现在我们已经知道，利用辗转相除法可以求出整数x，y，使得axby=(a,b).(4)为此所需要的除法次数是O(log10b).但是如果只需要计算(a,b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些.例1设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a,b).解：下面的四个基本事实给出了证明：(ⅰ)若ab，则(a,b)=a；(ⅱ)若a=2a1，，1，则(a,b)=2(2a1,b1)(ⅲ)若，则(a,b)=(a,b1)