(6)-初等数论ppt第三章-简化剩余类、欧拉函数、RSA

第三章(2)简化剩余类、欧拉函数及其应用、RSA,.,,(mod).,,(mod).9(mo5),dmmababmabmabmabm定义给定一个正整数把它叫做如果用去除任意两个整数与所得的余数相同,我们就说对模记作如果余数不同我们就说对模记作例72(mod5),712(mod5),7模同余不同余复习0(mod),0(mod).1,1(mod).,,0,1,2,.maamaaaabmbmbkmk可记为所以,所有的偶数可以表为2由于奇数满足2所以,所有的整数可以表为2对给定的和模所有同余于模的数就是算术数列(mod),(mod)(mod),(mod),(mod)(mod).0,,,()()aamabmbamabmbcmacmmaamabmbamabmbcmabbcac同余是一种等价关系,即有甲自反性乙对称性丙传递性证由以及112212121212121212121,,,,0,0,(mod),().,()(),.,,abmmababmttaqmrbqmrrmrmabmrrabqqmmabmmqqrrmrrrrmrrmababm定理整数对模同余的充要条件是,即是整数.证设若则,因此反之若则,因此,.但故定理1表明同余又可定义如下:若则对模同余11221212111222121212(i)(mod),(mod),(mod).(mod),-(mod).1,,,(),(i).(i)-()()()(mod).abmabmaabbmabcmacbmabmtabmtaabbmttcbcbabbam丁同余可以相加减若则(ii)若则证由定理因此即得由1122121211122212121221121212(mod),(mod),(mod),(mod),(mod).1,,.().(mod).abmabmaabbmabmakbkmabtmabtmaabbbtbtttmmaabbm戊同余可以相乘,若则特别地,若则证由定理因此故1111111111(mod),,,(,)1,(mod).1,,(),(,)1,,(mod).(i)(mod),0,(mod)(ii)(mod),,,(modabmaadbbddmabmmababdabdmmababmabmkakbkmkabmdabmabmddd己若则证由定理但故即庚则若是及的任一正公因数则).1212(mod),1,2,,,(mod[,,,]).1,,1,2,,,3[,,,],1(mod),,0,(mod).(mod),(,)(,),,ikikabmikabmmmmabikmmmababmdmdabdabmambmdmab辛若则证由定理再由第一章定理,即得故由定理即证得.壬若则癸若则因而若能整除及§,dab二数之一,则必能整除中另一个.(mod)(7)(mod/(,)).(,)1(mod),.(),().(,)(,)/(,),/(,)().(,)cacbmabmcmcmabmcmcabmcabcmcmmcmccmmabcm性质同余式等价于特别地,当时,同余式(7)等价于即同余式两边可约去证同余式(7)即这等价于由定理及()=1知,这等价于110000011,(,)1,1(mod),(mod).,,1.(mod)mamccamcamabmaxyaxmycxam性质若则存在使得我们把称为是对模的逆，记作或证由定理知,存在使得取既满足要求.由此提供一种求有效的方法,这是Euclid算法的又一重要应用.1212111'(mod);VII,(mod).)(mod)amccamccmamamccccmamaam显然,对模的逆不是惟一的.当是对模的逆时,任一也一定是对模的逆以及由性质知,对模的任意两个逆必有此外,显见(,)=1及(110100.1010,010(mod3).3.9nnnninnniiaaaaaaaaaaaaaa应用检查因数的一些方法A.一整数能被3(9)整除的必要且充分条件是它的十进位数码的和能被3(9)整除证显然我们只须讨论任一整数就够了.按照通常方法,把写成十进位数的形式;即因101(mod3),故定理得由性质知3当且仅当同法可得当且09.niia仅当11002130010001000,010007(1113)(1)-7(1113)(1)7(1113)nnnniniiiniiiaaaaaaaaaaaa应用检查因数的一些方法B.设正整数则7(或11,或13)整除的必要且充分的条件是或或整除(++)-(++)=证因为1000与1对模7(或11,或13)同余,故由定理知或或与对模或或同余.07(1113)7(1113)(1).niiiaa由性质，或或整除当且仅当或或整除110110-1-10=00=0,1010,0101010,01010+10++,010(modnnnnimmmmjllllknmlijkijkabPaaaaabbbbbPccccabcII弃九法(验算整数计算结果的方法)假设我们由普通乘法的运算方法求出整数的乘积是,并令，，，我们说：如果=00=0=00=09),.2,(mod9),(mod9).(mod9),(mod9)..nmijijlnmlkijkkijkababPcabcabPabP那么所求得的乘积是错误的因为定理及性质戊若则故不是0111,,,,,(0,1,,1)(i)(ii)mrmmKKKKrmqmrm定理若是一个给定的正整数则全部整数可分成个集合,记作其中是由一切形如的整数所组成的.这些集合具有下列性质：每一整数必包括在而且仅在上述的一个集合里面两个整数同在一个集合的充分与必要条件是这两个整数对模同余剩余类及完全剩余系112(i),,0.,,,,(mod),,.aaaararrraaamrrmaKraaKabKaqmrbqmrabmabK证设是任一整数由带余数除法即得故在内.又由同一定理知道是由惟一确定的因此只能在内.(ii)设是两个整数,并且都在内,则故则由同余的定义即知同在某一个内0110110111,,,,,,,,,,,..mmmmmKKKaaamaaammm定义定理中的叫做一个剩余类中任一数叫做它同类的数的剩余.若是个整数并且其中任何两数都不同在一个剩余类里,则叫做推论个整数作成模的一个完全剩余系的充分与必要条件是模的剩余类模的一个完全剩两两对模不同余余系10,1,,1(1)0,1,,,,(1)(1);(2)0,1,,(1),,(1)(1)(3),,1,,1,0,1,,1;(4)2221,,1,0,1,,1,;(5)222-1,,,1,0,12ammmamammmmmammmmmmmmmmmmm例序列都是模的完全剩余类.当是双数时序列-都是模的完全剩余类.当是单数时序列--1,,;(6)2mm都是模的完全剩余类.0101(,)1,,mmmambxmaxbmaamaabaabm定理2设是正整数,是任意整数若通过模的一个完全剩余系,则也通过模的一个完全剩余系,也就是说,若,,是模的一个完全剩余系,则,,也是模的完全剩余系.010111(mod),().1(mod).(,)1(mod).,,,mijijijmaabaabaabaabmijaaaamamaamaaa证由定理的推论,只要证明,,两两不同余就够了.假定由性质丁即得再由性质己及即得这与是完全剩余系的假设矛盾.故定理获证.§1212122112123,,,,mmxxmmmxmxmm定理若是互质的两个正整数而分别通过模的完全剩余系,则通过模的完全剩余系.12122112121212''''''2112211212''''''111222'''2121,,,1(mod)(7),,,1(mxxmmmxmxmmmmmmmxmxmxmxmmxxxxxxmxmx证由假设知道分别通过个整数.因此通过个整数.由定理的推论,只须证明这个整数对模两两不同余.假定其中是所通过的完全剩余系中的整数,而是所通过的完全剩余系中的整数,则由性质壬得§'''112122''''''12111222''''''''112212''''12od),(mod).1(,)1(mod),(mod).1,.,,mmxmxmmmxxmxxmxxxxxxxx又由性质己及即得由定理的推论得这表明如果与不全相同,(7)式即不成立.因此定理获证.§0,1,,1,,,-1,0,1,-1+1,,222-1,0,1,2-1-1,,,-1,0,1,-122mmmmmmmmmmmmm模的最小非负完全剩余模的定义这个整数叫做;当是偶数绝对时或叫做;当是最奇数时小完全剩余模的绝对最小完叫做全剩余;,0,1,2,,-1...),(,,mmaaammam定义是定义在正整数上的函数它在正整数上值等于序列中与互质的数的个数定义如果一个模的剩余类里面的数与互质就把它叫做在与模互质的全部剩余类中从每一类各任取一数所作成的数的集合叫做一个模互质的剩余类模的一个简拉函数化剩余系欧§3简化剩余系与欧拉函数011,,,.(,)1,(,)1,21(),().11,mrrrrrrKKKmKmrmkKkmmmmmmmmmmKmK证设是模的全部剩余类若是一个与模互质的剩余类,则.反之若有定理模的剩余类与模互质的充分必要条件是此类中有一数与互质.因此与模互质的剩余类的个数是模的每一简化剩余系是由则由定理及性质癸,中每一个与互质的个整数都与模不同互质余的整数组成的因而§§.(,)1rmKmrmm是与模互质的剩余类故定理的第一部分获证,且为与模互质的剩余类当且仅当.因此由欧拉函数的定义及模的简化剩余系的定义即得定理的其余部分.12112()12()2)2,,(,)1,(,)1,(,)1,1,(),,,3(,)1,.mmaxmamxmaxmaxaxxaaammmaaaxmamxmaxm定理若是与互质的整数,并且两两对模不同余,则是模的一个简化剩余系.定理若通过模的简化剩余系,则证通过(个整数,由于故若(modm通过模的简化剩),由性质己,(modm),余系这与原设§2,矛盾,故由定理定理获证.1212211212121221121221211,,,4,,,,xxmmmmxxmmmmxmxmmxmmmxmm证由定理我们立刻看出,简化剩余系是一定理若是两个互质的正整数,分别通过模的简化剩个完全剩余系中一切与模互质的整数作成的,因此只须证明:若分别通过模通过模的简化剩余系则+通过模的一个完全剩余系中一切与余系则+通过模的简化互质剩余系.的整数.121221121211221221112221121211222112122112122123,,,(,(,)1,,,,,,,,,xxmmmxmxmmxmxmmmmxmmxmmxmxmmxmxmmxmxmmmxmxmmmx由定理知,若分别通过模的完全剩余系则+通过模的完全剩余系.又若)=则由()=1即得(,)=()=1,于是()=1()=1.故()=1.反之,若()=1则(§121211222112122121122,,1,,)(,,(,)(,)1..mxmmxmxmmxmxmxmmmxmmx)=()=1.因而由性质癸()=1.因为()=1,所以定理获证§121221121221121211121222211212122114,,,+,+).