(2)最大公因数、辗转相除法、整除性质-、最小公倍数

最大公因数与辗转相除法整除的性质与最小公倍数复习,0(1)|.abbqabqbaabbabaabqbaabba定义设是任意两个整数，其中，如果存在一个整数使得等式成立，我们就说整除或可被整除,记作,此时我们把叫作的因数,把叫作的倍数.如果(1)里的整数不存在,我们就说不能整除或不被整除,记作111111111(),,,,.,,,,(),,.abbcacbacbcabacbabaabbbcaabcabca定理传递性若是的倍数是的倍数则是的倍数也就是[证]就是说存在两个整数使得成立因此但是一个整数故111111112,,.,,,,.(),,.abmabmabmabaambbmababmababm定理若都是的倍数则也是的倍数[证]是的倍数的意义就是存在两个整数使得因此但是整数故是的倍数121211223,,,,,,,,.nnnnaaamqqqnqaqaqam定理若都是的倍数是任意个整数则是的倍数,0,,0.(2).abbqrabqrrbqr(),,定理4带余数除法若是两个整数,其中则存在着两个整数及使得成立而且及是惟一的带余数除法的内涵它可以看作是整除的推广，也可以用带余除法定理来定义整除性将一个未知的整数表示为小于除数的余数，将整数进行分类，从而可将无限问题转化为有限问题其他应用：辗转相除法、进制间转换算法§2最大公因数与辗转相除法12121212121212.,,,(2).,,,,,,,,(,,,),(,,,)1,,,,,,.,,nnnnnnnaaannddaaaaaaaaaaaaaaaaaa定义设是个整数若整数是它们之中每一个的因数那么就叫作的一个整数的公因数中最大的一公因数个叫作记作若我们说若中每两个整数最大公互质，因数互质或我们就说它互素两们两互质12121212,,,,,)1,,,,,,)21nnnnaaaaaaaaaaaan显然,若整数,两两互质,则(反过来却不一定成立,且若,不全为零,则(是存在的.例1:2和互素;例2:6,10,-15是互素的,但它们任意两个数不互素,因为(6,10)=2,(10,15)=5,(-15,6)=3.1212121212,,,,,,,,,,,)(,,,)nnnnnaaanaaaaaaaaaaaa定理1若,是任意个不全为零的整数,则(i)与的公因数相同；(ii)(121212121212,,.,1,2,,,,1,2,,,,,,,,,,,.,,,,,niinnnnndaaadaindaindaaaaaaaaaaaaaaa证设是,的任一公因数由定义因而故是,的一个公因数,同法可证,的任一公因数都是的一个公因数故与,有相同的公因数,即(i)获证.由(i)立得(ii).(0(0,).,)(0,).bbbbbbbbbbbbbbbbbbb证显然0与的公因数是的因数.由于任何非零整数都是0的因数,故的因数也就是0，的公因数,于是(i)获证.其次,我们立刻知道的最大公因数是;而0，的最大公因数是的最大公定理2若是任一正整数,则(i)0与的公因数就是的因数,反之,的因数也是0与的因数,故推论2.1若是任一非零整数,则公因数.(ii)b.,,,.§13,(),3,,0,,,,,(,)(,).daabcabqcqabbbdadbdcaqcbbabcdbc定理设是任意三个不全为的整数且其中是非零整证设是的任一公因数由定义由定理是的因数,因而是的一个公因数.于是定理的前一部分获证数,则与有相.第二部分显同的公因数因而然随之成立.11112221-2-1-1-1-1+1+1,,,,0,,0,(1),0,,=0.nnnnnnnnnnnababqrrbbrqrrrrrqrrrrrqrr设是任意两个正整数由带余数除法我们有下面的系列等式：+1,,,=0.(1),...nbbr因为每进行一次带余数除法余数就至少减一，而是有限的所以我们最多进行次带余数除法，总可以得到一个余数是零的等式即式所指的计算方法叫作辗转相除法在西方常把它叫做欧几里得除法它就是我国著名的古代数学著作《九章算术》中提出的“更相减损术”辗转相除法的应用求出两个正整数的最大公因数推出最大公因数的重要性质解一次不定方程的基本工具辗转相除法在密码学中的应用RSA算法的重要部分还被用来解丢番图方程，寻找满足中国剩余定理得数，或者求有限域的倒数。还可以用来构造连分数，在一些整数分解算法中也有应用。同时在处理大数时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。111(0,)(,)(,)(,),(,)(,).,(.(,),)nnnnnnnrabababrarrrrrrbbabab定理4若是任意两个整数,则就是(证由定理2,3即得1)中最后一个不等于零的余数,即推论4.1的公因数与的因数相同辗转相除法求最大公约数问题步骤：时间复杂性：O(logn)252119854181984(252198)198354364252519854136181854(198354)31962181984541882554362例求和的最大公约数，并把它表为198和252的整系数线性组合.1-1859,1573,,2169,121,,abababab例求（）例求（）11111111111111(,).,0.(1)1,,,,,qnrrrrqnrmqnrnnnnmmnmmnmqnrrnmnnrrmmnnn证不妨设由带余除法得我们有2-12-2+2-122+2例设是正整数.证明(2-1-1.由此及2-12得(2-1,2-1)=(2-1,2-1).注意到()=(),若=0,,2-1)=2-1则()=结.论成立.11rnra若0,则继续对(2-1,2-1)作同样的讨论,由辗转相除法知，结论成立.显见,2用任一大于1的自然数代替,结论都成立.,,,,(),,,1,,abmambmabmababababababii定理5设是任意两个不全为零的整数(i)若是任意一正整数，则若是的任一公因数，则，特别1111222111,,(1),,,,,.,,,0,,04,,,nnnnababambmambmabmabmabmambmqrmrmbmbmrmqrmrmrmrmrmqambmrmabm证当有一为零时，定理显然成立，今设都不为零.由定理1,因此不妨假定都是正数.公式(1)里各式两边同乘以即得由定理得因而(i)获证.(),,,,,,,,,1,,=ababababababababababii由(i)及定理1,故当时，上式即为12122233112,,,.,,,,,,(2)nnnnaaanaaddaddad现在来研究两个以上整数的最大公因数.由定理及，不妨假设是任意个正整数令111121211121212121223,,,,.,,,,,,,,,,6,,,,,,,,,,,,nnnnnnnnnnnnnnnnnnnnnnndadddadddadddadadadaaadaaadadaaaanaadaddddd证由(2),.但故由此类推,最后得到即是的一个公因数.又设是的任一公因数则由推论4.1,同样由推论4.1由此类定理若是个整数推,最后得则12.,,,nnnndddddaaa.因而故是的最大公因数.§3整除的进一步性质及最小公倍数11112221111111,,,0,,0,(1),0,kkkkkknnnababqrrbbrqrrrrrqrrrrrq设是任意两个正整数则可以得到下列诸等式：10111201121,,1,1,,;(2)1,,,0,1,,(3)2,,kkkkkkkkkkkkabQaPbrknPPqPqPPQQQqQQkn定理若是任意两个正整数则其中2212122102221021222221022101111111,(2),2,[1]1,10,1,,2,11kkkkkkkkkkkkkraqbqqqqqPPqqqQQQaPbrPqPPQqQQkrrqrQaPbqQaPb证当时显然成立当时但故假定(2),(3)对于不超过的正整数都成立则1111111111111.1,,..kkkkkkkkkkkkkkkkkkqQQaqPPbQaPbrPqPPQqQQ故其中由归纳法，定理为真1.1,,,,(4)2,,,,1,(,,(),,(5),,.abstasbtababcacabcbcabcbcabc推论若是任意两个不全为零的整数则存在两个整数使得定理若是三个整数且则i)与有相同的公因数，ii上面假定了至少一个不为零(,,1,.13,,,.,,,,,,,,stasctbabscbtbdabcdbdbcbcabcbcbcabcabcbc证i)由题设及推论1.1存在任意两个整数满足等式两边乘以即得设是与的任一公因数.由上式及定理因而是的一个公因数反之的任一公因数显然是的一个公因数故(i)获证.(ii)因为不全为零,故是存在的,因而由(i)即知存在,且§112122212123,,,.,,,1,,1,,.2.2,,,,,1,2,,.,..2njnjnjnmnmcabcbccdcbaaabaaababjaccabcbaaabbbaaabbbm§推论2.1若则推论设及是任意两组整数若前一组中任一整数与后一组中任一整数互质,证由定理2及2定理2,3则与互质得故,因而证由定理2,再用定理，1212122312,,,1.nmnmnmaaabbbaaabbbaaab1212121212,,,2,,,,,,].3[,,,][,,,]..nnnnnaaanndndnaaaaaaaaaaaa定义设是个整数.若是这个数的倍数,则就叫作这个数的一个公倍数.又在的一切公倍数中的最小正数叫作最小公倍数,记作由于任何正数都不是0的倍数,故讨论整数的最小公倍数时,一概假定这些整数都不是零[定理111111,,,,,.,1,','',,.,,1,',mabmakbkaaabbbabakbabababababababakabbabab§证设是的任一公倍数.由定义可设定理4设是任意两个正整数,则(i)的所有公倍数就是的所有倍数;(ii)令,由的最小公倍数等于以它们的最大公因数除它们的乘积所得的商,即特别上式即得但由2定理5,的,若则1,,bk故由推论2.111',(6),.,,1,,().abmakabttabtkbttabtabababtabab因此其中满足等式反过来,当为任一整数时，为的一个公倍数，故(6)可以表示的一切公倍数.令即得到最小的正数，故即ii获证又由(6),(i)亦获证.121222331,,,.,,,,,,(7)nnnnaaanaammammam现在来研究两个以上整数的最小公倍数.设是任意个正整数令1112121212122323,2,3,,1,,,2,3,,,,,,,,,,,4(.,4(.,,,2,,,..iiiinnnnnnnnnmminamaminmaaamaaaamammmammaaannaaammmmmmm证由(7),且故是的一个公