初等數(shù)論教案 第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法

第二節(jié)最大公因數(shù)與輾轉(zhuǎn)相除法第三節(jié)最小公倍數(shù)教學(xué)目的：1、掌握最大公因數(shù)與最小公倍數(shù)性質(zhì)；2、掌握輾轉(zhuǎn)相除法；3、會(huì)求最大公因數(shù)與最小公倍數(shù).教學(xué)重點(diǎn)：最大公因數(shù)與最小公倍數(shù)性質(zhì)教學(xué)難點(diǎn)：輾轉(zhuǎn)相除法教學(xué)課時(shí)：6課時(shí)教學(xué)過(guò)程一、最大公因數(shù)1、定義1整數(shù)a1,a2,,ak的公共約數(shù)稱為a1,a2,,ak的公約數(shù).不全為零的整數(shù)a1,a2,,ak的公約數(shù)中最大的一個(gè)叫做a1,a2,,ak的最大公約數(shù)（或最大公因數(shù)），記為(a1,a2,,ak).注：1、由于每個(gè)非零整數(shù)的約數(shù)的個(gè)數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù).2、如果(a1,a2,,ak)=1，則稱a1,a2,,ak是互素的（或互質(zhì)的）；如果(ai,aj)=1，1i,jk，ij，則稱a1,a2,,ak是兩兩互素的（或兩兩互質(zhì)的）.顯然，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是素?cái)?shù)，a是整數(shù)，則(p,a)=1或pa；(ⅴ)若a=bqr，則(a,b)=(b,r).證明：(ⅰ)(ⅳ)留作習(xí)題.(ⅴ)由第一節(jié)定理1可知，如果da，db，則有dr=abq，反之，若db，dr，則da=bqr.因此a與b的全體公約數(shù)的集合就是b與r的全體公約數(shù)的集合，這兩個(gè)集合中的最大正數(shù)當(dāng)然相等，即(a,b)=(b,r).證畢3、定理2設(shè)a1,a2,,akZ，記A={y；y=，xiZ，ik}.如果y0是集合A中最小的正數(shù)，則y0=(a1,a2,,ak).證明設(shè)d是a1,a2,,ak的一個(gè)公約數(shù)，則dy0，所以dy0.另一方面，由第一節(jié)例2知，y0也是a1,a2,,ak的公約數(shù).因此y0是a1,a2,,ak的公約數(shù)中的最大者，即y0=(a1,a2,,ak).證畢推論1設(shè)d是a1,a2,,ak的一個(gè)公約數(shù)，則d(a1,a2,,ak).注：這個(gè)推論對(duì)最大公約數(shù)的性質(zhì)做了更深的刻劃：最大公約數(shù)不但是公約數(shù)中的最大的，而且是所有公約數(shù)的倍數(shù).推論2(ma1,ma2,,mak)=|m|(a1,a2,,ak).推論3記=(a1,a2,,ak)，則=1，特別地,=1.4、定理3(a1,a2,,ak)=1的充要條件是存在整數(shù)x1,x2,,xk，使得a1x1a2x2akxk=1.證明必要性由定理2得到.充分性若式(1)成立，如果(a1,a2,,ak)=d>1，那么由dai（1ik）推出da1x1a2x2akxk=1，這是不可能的.所以有(a1,a2,,ak)5、定理4對(duì)于任意的整數(shù)a，b，c，下面的結(jié)論成立：(ⅰ)由bac及(a,b)=1可以推出bc；(ⅱ)由bc，ac及(a,b)=1可以推出abc.證明(ⅰ)若(a,b)=1，由定理2，存在整數(shù)x與y，使得axby=1.因此acxbcy=c.(2)由上式及bac得到bc.結(jié)論(ⅰ)得證；(ⅱ)若(a,b)=1，則存在整數(shù)x，y使得式(2)成立.由bc與ac得到abac，abbc，再由式(2)得到abc.結(jié)論(ⅱ)得證.證畢推論1若(a,b)=1，則(a,bc)=(a,c).證明設(shè)d是a與bc的一個(gè)公約數(shù)，則da，dbc，由式（2）得到，d|c,即d是a與c的公約數(shù).另一方面，若d是a與c的公約數(shù)，則它也是a與bc的公約數(shù).因此，a與c的公約數(shù)的集合，就是a與bc的公約數(shù)的集合，所以(a,bc)=(a,c).證畢推論2若(a,bi)=1，1in，則(a,b1b2bn)=1.證明留作習(xí)題.6、定理5對(duì)于任意的n個(gè)整數(shù)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的一個(gè)公約數(shù).另一方面，對(duì)于a1,a2,,an的任何公約數(shù)d，由定理2的推論及d2,,dn的定義，依次得出da1，da2dd2，dd2，da3dd3，ddn1，danddn，因此dn是a1,a2,,an的公約數(shù)中的最大者，即dn=(a1,a2,,an).例1證明：若n是正整數(shù)，則是既約分?jǐn)?shù).解：由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1.注：一般地，若(x,y)=1，那么，對(duì)于任意的整數(shù)a，b，有(x,y)=(xay,y)=(xay,yb(xay))=(xay,(ab1)ybx)，因此，是既約分?jǐn)?shù).例2證明：121n22n12，nZ.解：由于121=112，n22n12=(n1)211，所以，若112(n1)211，(3)則11(n1)2，因此，由定理4的推論1得到11n1，112(n1)2.再由式(3)得到11211，這是不可能的.所以式(3)不能成立.注：這個(gè)例題的一般形式是：設(shè)p是素?cái)?shù)，a，b是整數(shù)，則pk(anb)kpk1c，其中c是不被p整除的任意整數(shù)，k是任意的大于1的整數(shù).例3設(shè)a，b是整數(shù)，且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設(shè)a和b是正整數(shù)，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，此時(shí)2kb1=(2b1)(2(k1)b2(k2)b1)=(2b1)Q，其中Q是整數(shù).所以2a1=2kb+r1=2r(2kb11)=2r((2b1)Q1)1=(2b1)Q(2r1)，其中Q是整數(shù).因此2b12a12b12r1在(ⅰ)中已經(jīng)證明這是不可能的，所以式(6)不能成立.綜上證得2b12a1.二、最小公倍數(shù)1、定義1整數(shù)a1,a2,,ak的公共倍數(shù)稱為a1,a2,,ak的公倍數(shù).a1,a2,,ak的正公倍數(shù)中的最小的一個(gè)叫做a1,a2,,ak的最小公倍數(shù)，記為[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|.證明留作習(xí)題.由定理1中的結(jié)論(ⅲ)可知，在討論a1,a2,,ak的最小公倍數(shù)時(shí)，不妨假定它們都是正整數(shù).在本節(jié)中總是維持這一假定.最小公倍數(shù)和最大公約數(shù)之間有一個(gè)很重要的關(guān)系，即下面的定理.3、定理2對(duì)任意的正整數(shù)a，b，有[a,b]=.證明：設(shè)m是a和b的一個(gè)公倍數(shù)，那么存在整數(shù)k1，k2，使得m=ak1，m=bk2，因此ak1=bk2.(1)于是.由于=1，所以，其中t是某個(gè)整數(shù).將上式代入式(1)得到m=t.(2)另一方面，對(duì)于任意的整數(shù)t，由式(2)所確定的m顯然是a與b的公倍數(shù)，因此a與b的公倍數(shù)必是式(2)中的形式，其中t是整數(shù).當(dāng)t=1時(shí)，得到最小公倍數(shù)[a,b]=.推論1兩個(gè)整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除.證明由式(2)可得證.這個(gè)推論說(shuō)明：兩個(gè)整數(shù)的最小公倍數(shù)不但是最小的正倍數(shù)，而且是另外的公倍數(shù)的約數(shù).推論2設(shè)m，a，b是正整數(shù)，則[ma,mb]=m[a,b].證明由定理2及前面的定理2的推論得到[ma,mb]==m[a,b].證畢4、定理3對(duì)于任意的n個(gè)整數(shù)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的一個(gè)公倍數(shù).另一方面，對(duì)于a1,a2,,an的任何公倍數(shù)m，由定理2的推論及m2,,mn的定義，得m2m，m3m，，mn即mn是a1,a2,,an最小的正的公倍數(shù).證畢推論若m是整數(shù)a1,a2,,an的公倍數(shù)，則[a1,a2,,an]m.證明：留作習(xí)題.定理4整數(shù)a1,a2,,an兩兩互素，即(ai,aj)=1，1i,jn，ij的充要條件是[a1,a2,,an]=a1a2an.證明：必要性因?yàn)?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如此繼續(xù)下去，就得到式(3).充分性用歸納法證明.當(dāng)n=2時(shí)，式(3)成為[a1,a2]=a1a2.a1a2=[a1,a2]=(a1,a2)=1，即當(dāng)n=2時(shí)，充分性成立.假設(shè)充分性當(dāng)n=k時(shí)成立，即[a1,a2,,ak]=a1a2ak(ai,aj)=1，1i,jk，ij對(duì)于整數(shù)a1,a2,,ak,ak+1，使用定理3中的記號(hào)，由定理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)及歸納假設(shè)推出(ai,aj)=1，1i,jk，ij.(8)綜合式(7)與式(8)，可知當(dāng)n=k1時(shí)，充分性成立.由歸納法證明了充分性.證畢定理4有許多應(yīng)用.例如，如果m1,m2,,mk是兩兩互素的整數(shù)，那么，要證明m=m1m2mk整除某個(gè)整數(shù)Q，只需證明對(duì)于每個(gè)i，1ik，都有miQ.這一點(diǎn)在實(shí)際計(jì)算中是很有用的.對(duì)于函數(shù)f(x)，要驗(yàn)證命題“mf(n)，nZ”是否成立，可以用第二節(jié)例5中的方法，驗(yàn)證“mf(r)，r=0,1,,m1”是否成立.這需要做m次除法.但是，若分別驗(yàn)證“mif(ri)，ri=0,1,,mi1，1ik”是否成立，則總共需要做m1m2例1設(shè)a，b，c是正整數(shù)，證明：[a,b,c](ab,bc,ca)=abc.解：由定理3和定理2有[a,b,c]=[[a,b],c]=，(9)由第三節(jié)定理5和定理2的推論，(ab,bc,ca)=(ab,(bc,ca))=(ab,c(a,b))=.(10)聯(lián)合式(9)與式(10)得到所需結(jié)論.例2對(duì)于任意的整數(shù)a1,a2,,an及整數(shù)k，1kn，證明：[a1,a2,,an]=[[a1,,ak],[ak+1,,an]].解：因?yàn)閇a1,a2,,an]是a1,,ak,ak+1,,an的公倍數(shù)，所以由定理2推論，推出[a1,,ak][a1,a2,,an]，[ak+1,,an][a1,a2,,an]，再由定理3推論知[[a1,,ak],[ak+1,,an]][a1,a2,,an].(11)另一方面，對(duì)于任意的ai（1in），顯然ai[[a1,,ak],[ak+1,,an]]，所以由定理3推論可知[a1,a2,,an][[a1,,ak],[ak+1,,an]]，聯(lián)合上式與式(11)得證.例3設(shè)a，b，c是正整數(shù)，證明：[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由此得證.三、輾轉(zhuǎn)相除法本節(jié)要介紹一個(gè)計(jì)算最大公約數(shù)的算法——輾轉(zhuǎn)相除法，又稱Euclid算法.它是數(shù)論中的一個(gè)重要方法，在其他數(shù)學(xué)分支中也有廣泛的應(yīng)用.1、定義1下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法.設(shè)a和b是整數(shù)，b0，依次做帶余數(shù)除法：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)中只包含有限個(gè)等式.下面，我們要對(duì)式(1)所包含的等式的個(gè)數(shù)，即要做的帶余數(shù)除法的次數(shù)進(jìn)行估計(jì).2、引理1用下面的方式定義Fibonacci數(shù)列{Fn}：F1=F2=1，F(xiàn)n=Fn1Fn2，n3，那么對(duì)于任意的整數(shù)n3，有Fn>n2，(2)其中=.證明：容易驗(yàn)證2=1.當(dāng)n=3時(shí)，由F3=2>=可知式(2)成立.假設(shè)式(2)對(duì)于所有的整數(shù)kn（n3）成立，即Fk>k2，kn，則Fn+1=FnFn1>n2n3=n3(1)=n32=n1，即當(dāng)k=n1時(shí)式(2)也成立.由歸納法知式(2)對(duì)一切n3成立.證畢.3、定理1(Lame)設(shè)a,bN，a>b，使用在式(1)中的記號(hào)，則n<5log10b.證明：在式(1)中，rn1，qn+12，qi1（1in），因此rn1=F2，rn12rn2=F3，rn2rn1rnF3F2=F4br1r2Fn+1Fn=Fn+2，由此及式(2)得bn=，即log10bnlog10，這就是定理結(jié)論.證畢4、定理2使用式(1)中的記號(hào)，記P0=1，P1=q1，Pk=qkPk1Pk2，k2，Q0=0，Q1=1，Qk=qkQk1Qk2，k2，則aQkbPk=(1)k1rk，k=1,2,,n.(3)證明：當(dāng)k=1時(shí)，式(3)成立.當(dāng)k=2時(shí)，有Q2=q2Q1Q0=q2，P2=q2P1P0=q2q11，此時(shí)由式(1)得到aQ2bP2=aq2b(q2q11)=(abq1)q2b=r1q2b=r2，即式(3)成立.假設(shè)對(duì)于k<m（1mn）式aQmbPm=a(qmQm1Qm2)b(qmPm1Pm2)=(aQm1bPm1)qm(aQm2bPm2)=(1)m2rm1qm(1)m3rm2=(1)m1(rm2rm1qm)=(1)m1rm，即式(3)當(dāng)k=m時(shí)也成立.定理由歸納法得證.證畢5、定理3使用式(1)中的記號(hào)，有rn=(a,b).證明：由第三節(jié)定理1，從式(1)可見rn=(rn1,rn)=(rn2,rn1)==(r1,r2)=(b,r1)=(a,b).證畢.現(xiàn)在我們已經(jīng)知道，利用輾轉(zhuǎn)相除法可以求出整數(shù)x，y，使得axby=(a,b).(4)為此所需要的除法次數(shù)是O(log10b).但是如果只需要計(jì)算(a,b)而不需要求出使式(4)成立的整數(shù)x與y，則所需要的除法次數(shù)還可更少一些.例1設(shè)a和b是正整數(shù)，那么只使用被2除的除法運(yùn)算和減法運(yùn)算就可以計(jì)算出(a,b).解：下面的四個(gè)基本事實(shí)給出了證明：(ⅰ)若ab，則(a,b)=a；(ⅱ)若a=2a1，，1，則(a,b)=2(2a1,b1)(ⅲ)若，則(a,b)=(a,b1)