(5)-第三章-同余、剩余类、完全剩余系

1、 初等数论 - 第三章(1) 同余、剩余类n同余：基本概念、性质、应用同余：基本概念、性质、应用n剩余系、完全剩余系：定义、性质剩余系、完全剩余系：定义、性质n简化剩余系、欧拉函数：定义、算法简化剩余系、欧拉函数：定义、算法n欧拉定理、费马定理：内容、证明、应用欧拉定理、费马定理：内容、证明、应用nRSARSA体制：算法、正确性证明体制：算法、正确性证明本章基本内容本章基本内容2n本章所介绍的同余这一特殊语言在数论中极为有本章所介绍的同余这一特殊语言在数论中极为有用，它是由历史上最著名的数学家之一卡尔用，它是由历史上最著名的数学家之一卡尔弗弗里德里希里德里希高斯（高斯（Kar Friedric

2、h GaussKar Friedrich Gauss）于）于1919世纪世纪初提出的初提出的. .n同余的语言使得人们能用类似处理等式的方式来同余的语言使得人们能用类似处理等式的方式来处理整除关系处理整除关系. . 在引入同余之前，人们研究整除关在引入同余之前，人们研究整除关系所用的记号笨拙而且难用系所用的记号笨拙而且难用. . 而引入方便的记号而引入方便的记号对加速数论的发展起到了帮助作用对加速数论的发展起到了帮助作用. .31 同余的概念及其基本性质同余的概念及其基本性质n今天（今天（20152015年年4 4月月8 8日）是星期三，问明年的日）是星期三，问明年的今天是星期几？（今天是星期

3、几？（20162016年年4 4月月8 8日）日）n明年的今天（明年的今天（20162016年年4 4月月8 8日）是星期五日）是星期五4,.,(mod).,(mod).9(mo5),dmmaba bmabma bmabm 定定义义 给给定定一一个个正正整整数数把把它它叫叫做做如如果果用用去去除除任任意意两两个个整整数数 与与 所所得得的的余余数数相相同同, , 我我们们就就说说对对模模记记作作 如如果果余余数数不不同同 我我们们就就说说对对模模记记作作 例例 72 (mod 5),712 (mod 5),7 72 (mod 5),712 (mod 5),7模模同同余余不不同同余余5n钟表对于

4、小时是模钟表对于小时是模1212或或2424的，对于分钟和秒是模的，对于分钟和秒是模6060的的n日历对于星期是模日历对于星期是模7 7的，对于月份是模的，对于月份是模1212的的n电水表通常是模电水表通常是模10001000的的n里程表通常是模里程表通常是模100000100000的的 同余在日常生活中的应用同余在日常生活中的应用60(mod),0(mod).1,1(mod).,0, 1, 2,.m aamaaaabmbmbkm k 可可记记为为 所所以以, ,所所有有的的偶偶数数可可以以表表为为 2 2 由由于于奇奇数数满满足足2 2所所以以, ,所所有有的的奇奇数数可可以以表表为为 2

5、2对对给给定定的的整整数数 和和模模所所有有同同余余于于模模的的数数就就是是算算术术数数列列7(mod),ii(mod)(mod),iii (mod),(mod)(mod0,()().aamabmbamabm aam abm bam ab mm bcmacbcm abbcamc同同余余是是一一种种等等价价关关系系, , 即即有有 自自反反性性 对对称称性性 传传递递性性 证证由由及及 以以i811221212121212121212,0,0,(mod),() .,1,()(),. , aq mr bq mrrmrmabmrrabqq mm abm m qqrrm rrrrmra bmm abr

6、m aba batmbmt 证证 设设若若则则, ,因因此此反反之之，若若则则, ,因因此此, ,. .但但故故定定理理1 1表表明明同同余余又又可可定定义义定定理理 整整数数对对模模同同余余的的充充要要条条件件是是, ,如如下下: :若若则则对对模模即即是是整整数数. .同同余余. .911122212121112122221 (i)(mod),(mod),(mod).(mod),- (mod 1,(),(i).(i) ) -().()()(mod).abm abmaabbmabcmac bmabmt abmtaabbm ttc bcbabbam 同同余余可可以以相相加加减减若若 则则 (

7、( 证证 由由定定ii)ii)若若则则理理因因此此即即得得由由10111222121 21 22 11 2121112212122 1,.(). (mod),(mod),(mod),(m (mod),(mod).od).abm ababt m abt ma abbbtb tt t m ma abbmma abbmabmakbkm 同同余余可可以以相相乘乘, , 若若 则则 特特别别证证 地地, ,由由定定若若 则则 理理因因此此故故 111111111111,1110102 (mod),(mod),1,2, ,(mod).(mod),0,1, ,(mod).kkkkkkkkiikkiinnnn

8、nnnnABmxym ikAxxByymabm ina xaxab xbxbm 定定理理若若 则则特特别别地地, ,若若 则则 121111111111(mod),( ,)1,(mod).(i)(mod),0,(mod) (ii)(mod),(mo1,(),( ,)1, ,(mod). d). m ababdabm aa d bbd d mabmabm kakbkmkabm da bmabmdddabd mm ababm 证证 由由定定理理 但但故故即即若若 则则 则则 若若 是是及及的的任任一一正正公公因因数数 则则 1312121,1,2, ,3 ,(mod),1,2, ,(mod ,).

9、(mod),0,(mod). (mod),( ,)( ,1 , )ikikabmikabm mmabm d m dabdabma mb mdmm ab ikm mmaba bd 证证 由由定定理理 再再由由第第一一章章定定理理, ,即即得得故故由由 若若 则则 若若 则则 若若 则则因因而而若若定定理理 即即证证能能整整除除及及二二得得. .数数之之一一, ,则则, a b必必能能整整除除中中另另一一个个. .14(),().( ,) ( ,)/ ( ,),(mod)(7)(mod/ ( ,).( ,)1(mod),./ ( ,)().( ,)cacbmabmc mc mabm c abmca

10、bc mc mmc m cc mmabc mmc性性质质 同同余余式式 等等价价于于 特特别别地地, ,当当时时, ,同同余余式式(7)(7)等等价价于于 即即同同余余式式两两边边可可约约去去 证证 同同余余式式(7)(7)即即这这等等价价于于由由定定理理及及()=1()=1知知, ,这这等等价价于于1500001101,1.(m1,( ,)1,1(mod),(mod).od)ma mccamcamabmx yaxmycxama 证证 由由定定理理知知, , 存存在在使使得得取取 既既满满足足要要求求. . 由由此此提提供供一一性性质质若若则则存存在在使使得得 我我们们种种求求 有有效效的的方

11、方法法, ,这这是是EuclEucl把把称称idid为为是是对对模模的的逆逆，记记作作 算算法法的的又又一一或或重重要要应应用用. .1611111( 10)1(mod11)( 5)6(mod11);1234567891016439287510paa 例例 求求模模所所有有元元的的逆逆元元. . 解解 由由1 (-10)+11=11 (-10)+11=1得得1 1由由2(-5)+11=12(-5)+11=1得得2 2同同样样计计算算得得：171212111(mod);,(mod).)(mod)amccamccmamamc cccmamaam 显显然然, , 对对模模的的逆逆 不不是是惟惟一一的

12、的. .当当 是是 对对模模的的逆逆时时, ,任任一一 也也一一定定是是 对对模模的的逆逆 由由性性质质知知， 对对模模的的任任意意两两个个逆逆必必有有 此此外外, ,显显见见( (, ,) )= =1 1及及( ( 18110100.1010,010(mod 3).3.9nnnninnniiaaaaaaaaaaaaaa 应应用用 检检查查因因数数的的一一些些方方法法 A A. . 一一整整数数能能被被3 3( (9 9) )整整除除的的必必要要且且充充分分条条件件是是它它的的十十进进位位数数码码的的和和能能被被3 3( (9 9) )整整除除 证证 显显然然我我们们只只须须讨讨论论任任一一整

13、整数数 就就够够了了. .按按照照通通常常方方法法, ,把把写写成成十十进进位位数数的的形形式式; ;即即因因1 10 01 1( (m mo od d 3 3) ), ,故故定定理理得得由由性性质质知知3 3 当当且且仅仅当当 同同法法可可得得 当当且且09.niia仅仅当当 1911002130010001000,010007(11 13)( 1)-7(1113)( 1)7(11 13)nnnniniiiniiiaaaaaaaaaaaa 应应用用 检检查查因因数数的的一一些些方方法法 B. B. 设设正正整整数数则则7(7(或或11,11,或或13)13)整整除除 的的必必要要且且充充分分

14、的的条条件件是是或或或或整整除除(+)-(+)=(+)-(+)= 证证 因因为为10001000与与 1 1对对模模7(7(或或11,11,或或13)13)同同余余, ,故故由由定定理理知知或或或或与与对对模模或或或或同同余余. .07(11 13)7(11 13)( 1).niiiaa由由性性质质， 或或或或整整除除当当且且仅仅当当或或或或整整除除2000105874192,5874192363,9,3,9435693,435693303,39637693,637 1000693,69363756niiniiniiniiaaA aaaAaaaaaa 例例1 1 若若则则能能被被整整除除. .

15、故故由由能能被被整整除除. . 例例2 2 若若则则能能被被 整整除除. .故故由由是是 的的因因数数. .但但不不能能被被 整整除除, ,故故9 9不不是是 的的因因数数 例例3 3 若若则则能能被被7 7整整除除而而不不.aa能能1111与与1313整整除除. .故故由由B,7B,7是是 的的因因数数, ,但但11,1311,13不不是是 的的因因数数21110110-1-10=00=0,1010,0101010,01010 +10 +,010 (mod nnnnimmmmjllllknmlijkijka bPaaaaabbbbbPccccabc II II 弃弃九九法法( (验验算算整整

16、数数计计算算结结果果的的方方法法) ) 假假设设我我们们由由普普通通乘乘法法的的运运算算方方法法求求出出整整数数的的乘乘积积是是 , ,并并令令，我我们们说说：如如果果=00=0=00=09),.2, (mod 9), (mod 9). (mod 9), (mod 9).nmijijlnmlkijkkijkababPcabcabPabP那那么么所所求求得得的的乘乘积积是是错错误误的的 因因为为定定理理 及及性性质质若若则则故故不不是是 2228997, =39495.,1145236415,17(mod 9),3(mod 9),32(mod 9).31732 mod 9 ,.aba bPabP

17、 例例5 5 若若如如果果按按普普通通计计算算方方法法得得到到的的乘乘积积那那么么我我们们按按照照上上述述方方法法但但 （ ）故故计计算算有有误误23406406244044064042(mod 10),09.91(mod 10),1(mod 10).1(mod 10).9(mod 10).aaa 例例 求求3 3写写成成十十进进位位数数时时的的个个位位数数. . 解解 要要求求 满满足足 3 3显显然然有有,33,33进进而而有有3 3因因此此，333333所所以以个个位位数数是是9.9.24406406244812(mod 100),099.1(mod 4),1(mod 5).41(mod

18、 25),.816(mod 25),3611(mod 25),669(mod 2dbbbdd 例例 求求3 3写写成成十十进进位位数数时时的的最最后后两两位位数数. . 解解 只只要要求求出出 满满足足 3 3注注意意到到1 10 00 0= =4 4 2 25 5, ,( (4 4, ,2 25 5) )= =1 1, ,显显然然有有, ,3 33 3注注意意到到 是是最最小小的的方方次次, ,由由第第一一章章 4 4例例5 5知知, ,使使3 3成成立立的的必必有有4 4因因此此计计算算3 33 33 316202020400406400665),544(mod 25),241(mod 2

19、5),1(mod 4),IX1(mod100),1(mod100).29(mod 100). 3 33 3由由此此及及3 3从从性性质质推推出出3 33 3因因此此3 33 33 33 3所所以以个个位位数数是是9 9, ,十十位位数数是是2 2. .2512511124510204040 3 5248,1(mod 41).5(mod 41);25(mod 41);27 (mod 41);9(mod 41);1(mod 41);1(mod 41).40,27 (mod 41).2(mod 23);4(mod 23);ddd 例例 求求6 mod 416 mod 41和和5 mod 23.5 m

20、od 23. 解解 首首先先找找到到一一个个整整数数满满足足6 6由由666666666666可可取取从从而而6 6 由由55555516202222 5 17 (mod 23);3(mod 23);12(mod 23);1(mod 23);22,5(mod 23).d 555555取取所所以以5 526102245122481625651264464410100001002,2 ,2 ,22(mod 645);24(mod 645);216(mod 645);2256(mod 645);2391(mod 645);216(mod 645);2256(b 1. 1.先先将将指指数数644644

21、表表示示成成二二进进制制形形式式 = = 2. 2.然然后后, ,用用逐逐个个平平方方及及模模645645约约化化来来计计算算的的最最小小正正剩剩余余. .求求2 2模模指指数数运运算算: :6 6 模模 4545644644512 128 45121284641284mod 645).64522222256 391 1616015361(mod 645)2256(mod 645);2391(mod 645);216(mod 645)3.3.现现在在用用2 2的的合合适适的的方方幂幂的的最最小小正正剩剩余余的的乘乘积积来来计计算算2 2模模2711022422,.,.kjNkkjbmb mNN

22、Na aa ab b bbmajbmm 即即计计算算模模的的一一般般过过程程, ,其其中中和和是是正正整整数数. .首首先先, ,将将 用用二二进进制制记记号号表表示示成成然然后后, ,用用逐逐个个平平方方及及模模约约化化求求出出模模的的最最小小正正剩剩余余. .最最后后, ,取取=1=1的的 所所对对应应的的模模的的最最小小正正剩剩余余的的乘乘积积, ,再再模模约约指指数数运运算算化化即即可可模模282222422122222,.loglog,22loglogloglogkNmNNkkmNNmb mNbmbmObmmb b bbmNOmON 定定理理 设设和和 是是正正整整数数, ,且且则则

23、计计算算模模的的最最小小正正剩剩余余要要用用次次位位运运算算. . 证证明明：用用上上面面所所描描述述的的算算法法来来求求模模的的最最小小正正剩剩余余. .首首先先, ,用用逐逐个个平平方方及及模模约约化化求求出出模模的的最最小小正正剩剩余余, ,其其中中. .这这总总共共需需要要比比特特的的运运算算, ,因因为为要要做做次次模模平平方方, ,每每次次平平方方需需要要次次位位运运算算. .然然后后, ,取取 的的二二进进制制2222222222mloglog,loglog.loglogjmNNmmNbOOO表表示示中中为为1 1的的数数字字对对应应的的的的最最小小正正剩剩余余的的乘乘积积, ,

24、在在每每次次乘乘法法之之后后模模约约化化. .这这也也需需要要次次位位运运算算因因为为至至多多有有次次乘乘法法, ,而而每每次次乘乘法法需需要要次次位位运运算算因因此此总总共共需需要要次次位位运运算算. .29011 1,(0,1,1) (i) (ii)mrmmK KKK rmqmrm 定定理理若若是是一一个个给给定定的的正正整整数数 则则全全部部整整数数可可分分成成个个集集合合, ,记记作作其其中中是是由由一一切切形形如如的的整整数数所所组组成成的的. .这这些些集集合合具具有有下下列列性性质质：每每一一整整数数必必包包括括在在而而且且仅仅在在上上述述的的一一个个集集合合里里面面两两个个整整

25、数数同同在在一一个个集集合合的的充充分分与与必必要要条条件件是是这这两两个个整整数数对对模模同同余余2 2 剩余类及完全剩余系剩余类及完全剩余系30112(i), 14,0.,(mod),.aaaararrraaa mrrmaKraaKa bKaq mrbq mrabma bK 证证设设 是是任任一一整整数数 由由第第一一章章定定理理 即即得得故故在在内内. .又又由由同同一一定定理理知知道道 是是由由 惟惟一一确确定定的的因因此此 只只能能在在内内. . (ii) (ii)设设是是两两个个整整数数, ,并并且且都都在在内内, ,则则故故则则由由同同余余的的定定义义即即知知同同在在某某一一个个

26、内内31011011011 1,. . mmmK KKma aama aammmm 定定义义定定理理中中的的叫叫做做模模的的剩剩余余类类一一个个剩剩余余类类中中任任一一数数叫叫做做它它同同类类的的数数的的剩剩余余. .若若是是个个整整数数 并并且且其其中中任任何何两两数数都都不不同同在在一一个个剩剩余余类类里里, ,则则叫叫做做模模的的一一个个完完全全剩剩余余系系推推论论个个整整数数作作成成模模的的一一个个完完全全剩剩余余系系的的充充分分与与必必要要条条件件是是两两两两对对模模不不同同余余321 0,1,1(1)0,1,(1)(1);(2)0,1,( 1),( 1)(1)(3),1, 1,0,

27、1,1; (4)2221, 1,0,1,1,;(5)222-1, 1,0,12ammmamammmmmammmmmmmmmmmmm 例例 序序列列 都都是是模模的的完完全全剩剩余余类类. .当当是是双双数数时时 序序列列- -都都是是模模的的完完全全剩剩余余类类. .当当是是单单数数时时 序序列列- -1,; (6)2mm都都是是模模的的完完全全剩剩余余类类. .330101( ,)1,mmma mbxmaxbmaamaabaabm 定定理理2 2 设设是是正正整整数数, , 是是任任意意整整数数若若 通通过过模模的的一一个个完完全全剩剩余余系系, ,则则也也通通过过模模的的一一个个完完全全剩剩余余系系, ,也也就就是是说说, ,若若,是是模模的的一一个个完完全全剩剩余余系系, ,则则,也也是是模模的的完完全全剩剩余余系系. .3401011 1(mod),().1(mod). ( ,)1(mod). ,mijijijmaaba