信息安全数学基础(第二章)

1、1第二章第二章 同余同余要求：掌握同余、剩余类、完全剩余系和简化剩余系等定义，熟练运用同余运算、欧拉定理、费马小定理以及模重复平方法。22.1 2.1 同余的概念及其基本性质同余的概念及其基本性质一、基本概念一、基本概念,|, (mod), (mod,2.1. ).1ma bm ababmabmmabm 不不 给给定定一一个个正正整整数数如如果果对对于于整整数数有有则则叫叫模模 同同余余，记记作作否否则则 叫叫做做模模记记作作义义同同余余定定 ， 7| 291 ,291 (mod7).1因因 （）所所以以 例例 7| 235 ,235 (mod7). 因因 （）所所以以 3二、基本定理及性质二

2、、基本定理及性质 ,(mod),2.1.1.ma babmkabkm 充充要要条条设设 是是一一个个正正整整数数, ,是是两两个个整整数数, ,则则的的是是存存在在整整 数数定定件件理理使使得得 (mod)|abmm ab证证 .abkmkabkm 存存在在整整数数 使使得得 678 83,673 (mod8).2因因所所以以例例4()(,(1) , (mod); (2) (mod), (mod); (3) (mod), (mod), (mod) 2.1.2 )() ma aamabmbamabm bcmacm 自自反反性性对对模模 同同余余是是关关系系 即即对对等等价价任任一一整整数数称称性

3、性若若理理则则若若则则定定传传递递性性 (1)|0,(mod).m aaaam证证 因因所所以以 (2)(mod),|,|,abmm abm ba若若则则有有于于是是 (mod).bam (3)(mod),(mod),|,|,abm bcmm ab m bc若若则则 |()(),(mod).mabbcacacm于于是是故故52.1.3,a bma bm整整数数模模 同同 余余的的是是被被除除充充要要条条件件的的余余定定理理 数数相相同同. . , 0, 0aqmrrmbq mrrm证证 设设 ()()abqq mrr则则 |.m abm rr于于是是|,rrm但但0 0|0,.m rrrrrr

4、所所以以 即即 4395 7,4257, 43因因 例例 3925 (mod7). 所所以以 6:整整数数间间的的同同余余关关系系还还有有以以下下性性质质1212112212121212, (mod), (mod),(i) (mod) (ii) (m2.1.4d ) oma ab babmabmaabbma ab bm 设设是是一一个个正正整整数数，是是 整整数数. .若若 则则 定定理理同余式可逐项相同余式可逐项相加、减、乘加、减、乘, (mod), (mod)abmakbkm 特特别别地地 若若则则111222+ (mod), ,abk mmabk m1122 (mod), (mod),a

5、bmabm 因因证证由由定定理理1 1711 21212212122112()()aabbkkma ab bk bk bk k m m于于是是 12122112,1kkk bk bk k m因因都都是是整整数数 所所以以由由定定理理 有有11 212212(mod)(mod)aabbma ab bm 39 224 1 (mod7),8584 (mod7)即即 394 (mod7)221 (mod7)5,因因 ，例例所所以以 392241 (mod7),615 (mod7)即即8 2003200358,26?年年 月月 日日是是星星期期五五 问问第第天天是是星星期期几几例例1 44(mod7)

6、2322(mod7),24 (mod7),281(mod7),解解 因因 2003667 32,又又 所所以以2003667 3 23667222(2 )2 20032故故第第天天是是星星期期二二.(.(星星期期五五加加4 4天天) )90101 (mod), (mod),0,1,2, , (mod)2.1.5iikkkkxym abmikaa xa xbb yb ym 则则定定理理若若 0101 (mod)kkkkaa xa xbb yb ym从从而而 (mod), (mod), 0iixymxymik 证证 设设 于于是是有有(mod), 0, iiabmik又又 所所以以有有(mod),

7、 0iiiia xb ymik1011101010101010, 0103|3|,9|92. |.1.6 kkkkikkkknnaaaaanaaanaaa 设设整整数数 有有十十进进制制表表示示式式: :则则 而而 定定理理 1110110101010(mod3)kkkkkkaaaaaaaa 101(mod3),(mod3),11(mod3),iiiaa证证 因因2.1.5由由定定理理有有0,ik11 1100 (mod3)kkaaaa 所所以以 11103|1010100 (mod3)kkkknaaaa 1103|kkaaaa 10101 (mod9),9|9|kknaaa 因因所所以以同同

8、理理可可证证 3| 36, 9| 36,3| 5874192, 9| 5874192.所所以以 5874192,5874192376n 设设因因 例例1210213010001000,01000,7(11,13)7(11,13)()()( 1)2.1.7 kkikiiinnaaaanaaaaa 0 0设设 有有10001000进进制制表表示示式式则则 或或或或整整除除或或或或整整除除 定定理理 352461000100010001 (mod7),1000100010001 (mod7), 即即 10001 (mod7), 证证 因因 所所以以 1000( 1) (mod7), 0.iiik 1

9、31110( 1)( 1)( 1)kkkkaaaa 于于是是1110100010001000kkkkaaaa 213()() (mod7)aaaa0 0 10001 (mod11),10001 (mod13),1113mm 因因 所所以以结结论论对对于于或或也也成成立立. .14 637693637 10008693,n 例例设设有有 169363756aa0 0 7 | 56,11 | 56, 13 | 56,因因而而故故 7 | 637693,11 | 637693, 13 | 637693.但但15 (mod), ( ,)1, 2.1(o.d)8mmadbdmd mabm 设设是是一一个

10、个正正整整数数, ,如如果果则则 定定理理 ( ,)1,|,d mm ab因因 所所以以故故 (mod),|,adbdmm adbd证证 若若 则则即即| ()m d ab (mod)abm m上上面面几几个个性性质质, ,其其模模不不发发生生变变化化, ,属属于于基基本本性性质质. .16模模发发生生变变化化以以下下是是的的几几个个性性质质. . (mod),0,2.1(.9 mod)mmabm kakbkk 设设 是是正正整整数数, ,则则 定定理理 (mod)akbkmk (mod)|abmm ab证证 由由|()mkab kakbk17 (mod), (m2.1.od10).mabmd

11、a, bmabmddd 设设是是正正整整数数, ,如如果果是是及及 的的任任一一则则公公因因数数 定定理理, ,a b md dd因因都都是是整整数数 故故 (mod),abmk 证证 因因所所以以存存在在整整数数使使得得abmk,abmkddd于于是是 (mod)abmddd 18 (mod), 0, (mo2.1.1d.1)mabm d |m, dabd 设设是是正正整整数数, ,如如果果则则 定定理理 (mod )abd 故故 (mod),|.abmm ab证证 因因所所以以 |,|.d md ab 又又因因 于于是是 19050 (mod70), 9 9因因例例 195 (mod7),

12、 19050 (mod7)所所以以 191212, 2.1. (mod),1,2, , (mod,)12.kikm mmabmikabm mm 设设是是正正整整数数, ,且且则则 定定理理 12(mod,)kabm mm 故故 ,(mod),1,2,iabmik证证 因因则则 |,1,2,imab ik12,|km mmab 于于是是 201212, (mod),1,2, , (mod).()kikm mmabmikabm mm 设设是是两两两两的的正正整整数数且且 则则 推推论论互互证证 明明作作业业题题素素 ,(mod),(mod )(mod10).p qabpabqabpq 设设是是不不

13、同同的的素素数数 如如果果有有则则 例例 2.1.12(mod , ),abp q 证证 由由题题设设及及定定理理, ,有有 ( , )1, , .p qp qpq又又因因所所以以故故 (mod)abpq 21 (mod),2 ( ,)( ,). .1.13mabm a mb m 设设是是正正整整数数, ,则则 定定理理 (mod),abmkabmk 证证 因因则则存存在在整整数数使使得得 | ,| ;| ,| .h a h mh bh b h mh a上上式式表表明明: :由由由由 ,a mb m即即与与有有相相同同的的公公因因数数 从从而而 ( ,)( ,)a mb m 22 , ,0,1

14、 (mod),0,1 (mod)11aam n anmnppm 设设都都是是正正整整数数 如如果果则则存存在在 的的一一个个素素因因数数使使得得例例即即有有 (),np证证若若存存在在 的的一一个个法法素素因因数数反反证证使使得得0(mod)apm |amp则则. .| ,|,|,aaap npnm n又又因因有有于于是是0(mod),.anm 与与题题设设矛矛盾盾23 0 (mod).apm ,np每每个个素素因因数数又又如如果果对对 的的都都有有 1 (mod)apm 1(mod)2. .4,1anm 则则由由有有与与题题定定理理设设矛矛盾盾. .,np于于是是存存在在 的的一一个个素素因

15、因数数使使得得p又又由由前前面面证证明明可可知知, ,这这个个 也也满满足足 1 (mod).apm ,0(mod).anppm 这这说说明明对对 的的都都有有所所有有素素因因数数24是是大大自自然然的的循循环环现现象象, ,研研究究同同优优点点 余余的的在在于于: :化化同同无无余余”限限注注: : “为为有有限限. . 运运算算后后把把同同余余式式译译为为等等式式又又将将等等式式译译为为同同余余式式. .证证明明同同余余式式的的一一般般方方法法( (基基本本的的方方法法):):其其理理论论根根据据是是: : (mod)|abmm ab 25三、验算整数计算结果的方法（弃九法）三、验算整数计

16、算结果的方法（弃九法） 1101101101010(,010)1010(,010)1010(,010)nnnninnnnillllia aaa aZab bbb bZbabcccc cZc 设设 原原理理= = =000)(mod9),nnlijkijkabc 如如果果(则则所所求求的的结结果果是是错错误误的的。怎怎样样检检验验错错误误：26110( )nnnnf xa xaxaZ X 设设事事实实上上：101(mod9),(10)(1)(mod9)ff 0(mod9)niiaa 即即0(mod9)njibb 同同理理可可证证：0(mod9)lkkabc 根根据据同同余余的的性性质质：27但但

17、若若故故所所求求计计算算结结果果是是错错误误的的。00)()(mod9)nnijijabab （000)()(mod9)nmlijkijkabc （2368 8462003328.作作（）用用弃弃九九法法验验算算业业下下列列等等式式：题题282.2 2.2 剩余类及完全剩余系剩余类及完全剩余系一、基本概念一、基本概念(),m 把把同同余余 关关于于模模的的整整数数放放在在一一起起 可可以以把把整整数数分分类类. ., | (mod),amaCc acm cZ设设是是一一个个正正整整数数 对对任任意意整整数数令令,.aaaCC 因因所所以以29,(i) 1(ii) (mod);(iii) (m2

18、.2.o1 d);rababmCrmCCabmCCabm 设设 是是一一个个正正整整数数 则则任任一一整整数数必必包包含含在在一一个个定定中中 理理 ,0; ,0; (mod),.rramaC因因此此 于于是是 (i),0aamqrrm证证 设设 为为任任一一整整数数 由由欧欧几几里里得得除除法法 有有 (ii),ababCCaCC设设则则 (mod).abm 从从右右到到左左反反之之(),(),设设,acC 对对任任意意则则 (mod).abm 于于是是30.abCC 与与假假设设矛矛盾盾 故故 (mod)acm (mod),bcm 于于是是,bcC 所所以以.abCC 故故.baCC 同同

19、理理可可证证.abCC 从从而而 (iii)(ii)由由即即得得必必要要性性. . (mod).,ababmCC ( (反反证证法法) ) 设设若若下下证证充充分分性性. .,abcCcC则则有有于于是是有有 (mod)(mod)acmbcm及及 (mod),abm 从从而而31011011 | mod , , , , ,2.2.1, ammCc acm cZmar rrmr rrm 叫叫做做模模的的 的的一一个个剩剩余余类类中中的的任任一一数数叫叫做做该该类类的的或或若若是是 个个整整数数 并并且且其其中中任任何何剩剩余余类类. .剩剩余余代代表表两两个个数数都都不不在在同同一一个个剩剩余余

20、类类里里 则则叫叫 做做模模的的一一个个元元. .完完全全 定定义义剩剩余余系系. . 0111.,2:,.mmmC CCmmmm 模模 的的剩剩余余类类有有 个个 在在同同一一剩剩余余类类中中的的数数互互相相同同余余, ,不不在在同同一一剩剩余余 类类的的数数注注互互不不同同余余. .模模 的的完完全全剩剩余余系系恰恰有有 个个整整数数. .个个连连续续的的整整数数也也是是模模 的的完完全全剩剩余余系系. .32 ,1, 1,0,1,1222 1, 1,0,1,1,222mmmmmmmm为为偶偶数数时时或或都都是是模模 的的完完全全剩剩余余系系. .例例如如 11 , 1,0,1,22mmm

21、m为为奇奇数数时时也也是是模模 的的完完全全剩剩余余系系. .33 10,1011|0amaCak kZm 设设对对任任意意整整数数集集合合是是 例例模模的的剩剩余余类类. .010|20, 10,0,10,20,0CkkZ110|191, 9,1,11,21,CkkZ910|119, 1,9,19,29,CkkZ0,1,2,3,4,5,6,7,8,910是是模模的的一一个个完完全全剩剩余余系系. .1,2,3,4,5,6,7,8,9,1010是是模模的的一一个个完完全全剩剩余余系系. .34二、有关完全剩余系的几个定理二、有关完全剩余系的几个定理 011, ,(mod), ,0,1,.12

22、2.2mijmmr rrmrrmij i jm 设设 是是一一个个正正整整数数 则则个个整整数数为为模模 的的一一个个完完充充要要条条件件 全全剩剩余余系系的的是是 定定理理011,mr rrm 证证 是是模模 的的一一个个完完全全剩剩余余系系,()ijr r ij 它它们们中中任任意意两两个个数数不不在在同同一一剩剩余余类类（定定义义） (mod), ,0,1,1.ijrrm ij i jm （）定定义义35mm 设设 是是一一个个正正整整数数, ,则则常常用用的的几几个个模模 的的完完 例例2 2全全剩剩余余系系: : 0, 1, 2, , 1m 最最小小非非负负完完全全剩剩 余余系系(

23、(1 1) ) 1, 2, , 1, mm 最最小小正正完完全全剩剩余余系系( (2 2) ) (1), (2), , 1, 0mm ( (3 3 最最大大非非正正完完) )全全剩剩余余系系 , (1), , 2, 1mm 最最大大负负完完余余系系4 4) )全全剩剩( (36 , 1, , 1, 0, 1, , 1222 1, , 1, 0, 1, , 1, ,222mmmmmmm为为偶偶数数时时, ,为为或或 ,11 , , 1, 0, 1, , 22mmm为为奇奇数数时时 为为(5) 绝绝对对值值最最小小完完全全剩剩余余系系37(2,)1, .2.3ma mbxmaxbm 设设 是是正正

24、整整数数, ,是是任任意意整整数数, ,若若 遍遍历历模模 的的一一个个完完全全剩剩余余系系, ,则则也也遍遍历历模模的的一一个个定定理理完完全全剩剩余余系系. .01-1011, mmaaamaa + baa + baa+ bm 即即: :若若是是模模 的的完完全全剩剩余余系系, ,则则， ，也也是是模模 的的完完全全剩剩余余系系. . (mod,):) (.ijaabaabmij 分分只只需需明明析析证证即即可可 ,( ,)1.a m 可可用用反反证证法法 利利用用38 (mod),()ijaamij(),ijaaij 证证 若若存存在在 和和使使得得 (mod),()ijaabaabmi

25、j| ().ijm a aa 则则,|,( ,)1ija mm aa 因因所所以以于于是是01-1,maaam这这与与是是模模 的的完完全全剩剩余余系系的的假假设设矛矛盾盾. .011 maa + baa + baa+ b ， ，故故m是是模模 的的完完全全剩剩余余系系. .39 10,7,5.:310mabx设设当当 遍遍历历模模的的完完全全 例例剩剩余余系系 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,510 x 时时 形形如如7 7的的个个整整数数10也也构构成成模模的的完完全全剩剩余余系系. . 5, 12, 19, 26, 33, 40, 47, 54, 61, 684

26、0 12, ,( ,)1,(1),1,2,mixxxma b mZa maxbmm mmm（）若若是是 的的完完全全剩剩余余系系，且且则则除除以以 的的余余数数之之和和1 1作作业业题题为为中中2 2 其其 4112121212121221(,)1,0,0,2. .,2 4m mmmxxmm mmxxm m 定定理理分分若若而而遍遍历历模模的的完完全全剩剩余余系系 则则遍遍历历模模的的完完全全余余. .别别剩剩系系 , ,12m m所所以以只只需需证证明明这这个个121221,xxm mm x 证证 因因遍遍历历个个整整数数时时分分别别1212m xm m遍遍历历个个整整数数. .12.m m

27、整整数数对对模模两两两两不不同同余余即即可可1212,xxyy若若有有整整数数, ,使使得得 2112211212(mod)m xm xm ym ym m42112|,2.12.1.11mm m根根据据则则因因所所以以（节节定定理理） 212211112(mod)m xxm yymmm 21211(mod)m xm ym 所所以以 )1211|(mmxy 于于是是 12111(,)1,|.m mmxy但但因因 所所以以 111(mod),xym 于于是是 222(mod)xym 同同理理 故故定定理理成成立立. .43 , ,(4mod ), 0, 0p qnpqcx yqxpyxpcnyq

28、设设是是两两个个不不同同的的素素数数则则对对任任意意的的整整数数存存在在唯唯一一的的一一对对整整数数满满足足 例例 ,( , )1.p qp q 证证 因因是是两两个个不不同同的的素素数数 所所以以 2.2.4,x yp q由由定定理理及及其其证证明明 知知分分别别遍遍历历的的完完全全剩剩余余系系, c因因此此对对于于整整数数, x y存存在在的的一一对对整整数数唯唯一一满满足足 (mod ), 0, 0qxpycnxpyq,qxpynpq时时遍遍历历的的完完全全剩剩余余系系. .442.3 2.3 简化剩余系与欧拉函数简化剩余系与欧拉函数一、欧拉一、欧拉(Euler)函数函数0,1,2,12

29、.3.1().Eulermmmmm 设设 是是一一个个正正整整数数, ,则则个个整整数数中中与与 互互素素的的整整数数的的个个数数, ,记记作作通通常常称称 定定义义欧欧为为拉拉函函数数. . ( ( )()0,1,2,1Eulerxmmm 定定义义在在正正整整数数上上的的函函数数 即即: :欧欧拉拉函函数数是是, ,的的值值等等于于中中与与互互素素的的数数的的个个数数. .()() (10)4,(7)6例例1 1 45二、简化剩余系二、简化剩余系2.3.2mmm如如果果模模 的的剩剩余余类类里里面面的的数数与与 互互素素, , 与与模模 互互素素的的就就剩剩把把这这余余类类个个类类叫叫做做一

30、一个个.(.(又又称称简简化化 定定义义) )剩剩余余类类 2.3.3mmm简简化化剩剩余余类类设设 是是一一个个正正整整数数 在在模模 的的所所有有不不同同中中, ,从从每每个个类类任任取取一一个个数数组组成成的的整整数数的的集集合合, ,叫叫简简化化剩剩做做模模定定义义. .余余系系的的一一个个 , , 019137910,101,3,7,910mCCCC CCC 模模的的剩剩余余类类中中, ,是是例例2 2模模的的简简化化剩剩余余类类. .是是模模的的一一个个简简化化剩剩余余系系. .461212,)1( ,)2.3 1.1r rmr mr m 设设是是同同一一模模 剩剩余余类类的的两两

31、个个剩剩余余, ,则则( ,( , 定定理理12( ,)1( ,)1r mr m故故 12(mod)rrm 证证 由由题题设设 , ,于于是是有有12( ,)( ,)(1.3.3).r mr m 定定理理因因而而12rrkmmm此此定定理理说说明明: :模模 的的简简化化剩剩余余类类中中的的数数都都与与互互素素. .470,1,2,1mmmm 为为此此, ,只只需需在在模模 的的里里找找出出与与的的所所有有整整数数, ,则则这这些些整整数数的的全全体体就就最最小小非非构构成成模模负负完完全全剩剩余余系系的的一一个个简简剩剩余余系系互互素素化化. . mm 由由欧欧拉拉函函数数的的定定义义知知,

32、 ,模模 的的简简化化剩剩余余系系里里共共含含()()个个数数. . 1, 7, 11, 13, 17, 19, 23, 29303 是是模模的的简简化化剩剩 余余系系. (30. (30 例例)=8.)=8. RSA ,1, 2, 3,41( )1mppppp 当当为为素素数数时时是是模模的的简简化化剩剩余余系系. .所所以以（ 应应用用于于密密. . 例例码码系系统统）48:几几类类特特殊殊的的简简化化剩剩余余系系 (1)0,1,2,1mmmmm 个个整整数数中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系, ,叫叫最最小小非非负负简简化化做做模模 的的剩

33、剩余余系系. . 5m设设是是一一例例个个正正整整数数, ,则则 (2)1,2,1,mmmmmm 个个整整数数中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系, ,最最小小正正简简化化叫叫做做模模 的的剩剩余余系系. . (3)1), 1,0mmmmm个个整整数数-(-(中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系, ,最最大大非非正正简简化化叫叫做做模模 的的剩剩余余系系. .49 (4), (1), 1mmmmmm个个整整数数-中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系最最大大负

34、负简简化化, ,叫叫做做模模 的的剩剩余余系系. . , (5),1, 1,0,1,12221, 1,0,1,1,222mmmmmmmmmmm当当 为为偶偶数数时时个个整整数数-或或个个整整数数 - -中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系. .50, 11, 1,0,1,22mmmmmm 当当 为为奇奇数数时时个个整整数数- -中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系. .m 这这两两个个简简化化剩剩余余系系统统称称为为绝绝对对值值最最小小模模 的的简简化化剩剩余余系系. .51三、有关简化剩余系的定理三、

35、有关简化剩余系的定理12() ( ,)1, 1,2,3, (), (mo2.3.d) (),2iijmmr mimrrmijr rrm 设设 是是一一个个正正整整数数, ,且且则则是是模模的的一一个个 简简 定定. .理理化化剩剩余余系系 ()mm 证证 （）因因模模 的的简简化化按按定定义义剩剩余余证证系系恰恰含含个个整整数数. .12() (mod) (),()ijmrrmijr rrmm 又又因因所所以以是是模模的的不不同同剩剩余余系系中中的的个个数数. .,()mmm 由由题题设设 这这个个数数都都与与互互素素. .故故它它们们组组成成模模 的的一一个个简简化化剩剩余余系系. .52(

36、 ,)12.3.3ma mxmaxm 设设 是是一一个个正正整整数数,若若 遍遍历历模模的的简简化化剩剩余余系系, ,则则也也遍遍历历模模 的的简简 定定理理化化剩剩余余系系. .( ,)1,( ,)1,(,)1.a mx max m因因所所以以有有12()12()(),(),mmxmxmxxxaxmax axax 证证 当当 遍遍历历模模 的的简简化化剩剩余余系系时时, , 遍遍历历个个整整数数, ,从从而而遍遍历历个个整整数数. . (mod), ().ijaxaxmij 所所以以只只需需证证明明 即即可可 ,(mod) (),ijaxaxmij反反（证证法法）若若( ,)1,2.1.8a

37、 m 则则因因根根据据定定理理，53这这与与题题设设矛矛盾盾. . (mod),(),ijxxmij所所以以axm故故遍遍历历模模 的的简简化化剩剩余余系系. . 17(mod30),74919(mod30),117717(mod30),13911(mod30),1711929(mod30),1913313(mod30),2316111(mod777730),2920323(mod307)777 30,7,1,7,11,13,17,19,23,2930,(7,30)1,6ma 设设模模已已知知是是模模的的 例例简简化化剩剩余余系系有有 7, 49, 77, 91, 119, 133, 161,

38、 20330 所所以以是是模模的的简简化化剩剩余余系系. .54( ,)1,1, 1 (mod)2.3.4ma maamaam 设设 是是一一个个正正整整数数,则则存存在在整整数数使使得得 定定理理( ,)1,a mxm 因因当当 遍遍历历模模 的的() 存存在在证证性性证证明明一一,axm一一个个最最小小正正简简化化剩剩余余系系时时也也遍遍历历模模 的的一一个个简简化化剩剩余余系系. .,1,1xaamaa因因此此存存在在使使得得属属于于 的的,剩剩余余类类 1 (mod).aam 即即55()构构造造证证 性性证证明明二二( ,)1satma m( ,)1, ,a ms t 因因则则存存在

39、在整整数数 1 (mod)aam 0 (mod),1 (mod),tmmsam因因 所所以以 (mod),asm 取取则则有有使使得得 如何找到如何找到a呢？利用广义呢？利用广义Euclid除法除法：思考题：唯一性？思考题：唯一性？56 7,7mam 设设表表示示与与互互素素的的整整数数. .则则有有相相应应 例例的的同同余余式式 11 (mod7), 21 (mod7), 31 (mod7),41 (mod7), 51 (mod7), 6141 (mo375)26d 224 (mo513d737),a 取取则则 737,635,224,193,( 224)63519373718mast 设设

40、由由广广义义欧欧几几里里得得除除法法, ,得得整整数数例例可可使使 635 5131 (mod737)5712121212211212(,)1, 0, 2.3.50, ,m mmmxxm mm xm xm m 设设若若分分别别遍遍历历的的则则遍遍历历 定定理理简简模模的的. .化化剩剩余余系系简简化化剩剩余余系系, , 21121212m xm xm mm m 因因简简化化剩剩余余系系是是一一个个中中一一切切与与模模互互素素的的数数组组成成的的. . 为为此此只只需需证证明明: :遍遍历历模模的的一一个个完完全全剩剩余余系系中中一一切切与与分分完完全全剩剩余余系系互互析析: :素素 模模 的的

41、整整数数. .1122211212(1) (,)(,)1(,)1x mxmm xm xm m12(,)1m m 利用利用,:为为此此 证证明明分分两两个个部部分分5821121122 (2) (,)1,(,)1.m mm x + m xx mxm模模的的任任一一简简化化剩剩余余系系可可表表为为其其中中1212 由定理由定理2.2.41121121(,)1(,)1(,)1x mm x mmm 证证 首首先先12112(,)1m xm xm2212212(,)1 (,)1(,)1xmm xmm m 12122(,)1m xxmm211212(,)1m xm xm m（根据第一根据第一章关于最大公因

42、数的定章关于最大公因数的定理理）592112 m mm x + m x其其次次, ,模模的的任任一一剩剩余余（）可可表表示示为为完完全全剩剩余余1212211212,)1,m x + m xm m 因因此此, ,当当( (时时2112121122(,)1(,)1m xm xmm xm xm 211122(,)1(,)1m x mm xm 1122(,)1(,)1x mxm 12(,)1m m 因因60四、欧拉函数的性质及计算方法四、欧拉函数的性质及计算方法, 2.3 (, )1 .6)() ( ).m nmnmn 欧欧拉拉若若则则数数定定的的质质理理函函( (性性 ) ) ( (,)( )xm

43、yn另另一一方方面面遍遍历历个个整整数数遍遍历历个个整整数数. .(,(,) ( )nxmymn 所所以以遍遍历历 ( (个个整整数数. .2.3.5,x ym n证证 由由定定理理知知, ,当当分分别别遍遍历历模模的的简简化化剩剩 nxmymn 余余系系时时遍遍历历模模的的简简化化剩剩余余系系,nxmy 即即)mn 遍遍历历 ( (个个整整数数. .)() ( ).mnmn 故故( ( 61(77)(7) (11)6 1060例例 9 9(30)(2 3 5)(2) (3) (5)例例 101012122.3.7kknnppp 设设正正整整数数 的的标标准准分分解解式式为为 定定 理理则则

44、,( ):x 一一般般地地 欧欧拉拉函函数数可可按按下下述述方方法法计计算算1 2 48( )1.nppp 特特别别地地 当当为为素素数数时时,12111( )(1)(1)(1)knnppp 62 1212(,)1, (),2.3.6( )() ()()jikijkppijnppp 证证 因因 所所以以由由定定理理1().pppp 下下面面证证明明, ,当当 为为素素数数时时, , 111, 1,1,1,(1),0,(1)1,(1()(11pppppp pp ppp p ,:npn 当当时时 模模 的的完完全全剩剩余余系系为为21,p|1p p 共共个个整整数数. .63 10,(1)pp p

45、 1.p 共共个个1.pp np 因因此此模模的的简简化化剩剩余余系系的的元元素素个个数数为为:n不不互互素素其其中中与与的的整整数数有有1().ppp 即即 12111(1)(1)(1)knppp1212( )() ()()kknppp 11221111122()()()kkkkpppppp 于于是是64,()1p qpqpqpq 若若是是不不同同的的素素数数 则则 推推论论()( ) ( )pqpq 证证 (1)(1)1pqpqpq ,1( )npqpqnnpqn 如如果果则则 2,(1()0).p qxnxnn 于于是是是是一一元元二二次次方方程程的的根根:注注65 |2.3.8,( )

46、d nndn 定定设设 是是一一个个正正数数理理整整则则 |d nn 其其中中表表示示对对 的的所所有有正正因因数数求求和和. .1 2, .nCnn 证证 对对 个个整整数数的的集集合合， ，按按照照与与 的的最最大大公公因因数数进进行行分分类类 | ,|1,(, )dd nCmmn m nd对对于于正正整整数数记记(, )(,)1,dm nm ndCmdd因因所所以以中中元元素素 的的形形式式为为66 |1,( ,)1dnnCmdkkkdd().dnCd 因因此此中中元元素素个个数数为为|()( )d nd nnndd1,2,n因因中中的的每每个个数数,dC属属于于且且仅仅属属于于一一个个

47、类类所所以以|()d nnnd ,ndnnd注注意意到到 当当 遍遍历历 的的所所有有正正因因数数时时也也遍遍历历 的的所所有有,正正因因数数 故故675050C 50,1,2,5,10,125,50.1nn 设设整整数数则则 的的正正因因数数为为 例例于于是是 11,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,C 22,4,6,8,12,14,16,18,22,24,26,28,32,34,36,38,42,44,46,48,C 55,15,35,45,C 1010,20,30,40,C 2525,C 685050|()(1)1

48、,50C于于是是250|()(25)20,2C550|()(10)4,5C1050|()(5)4,10C2550|()(2)1,25C150|()(50)20,1C|50( )(1)(2)(5)(10)(25)(50)dd 50 692.4 2.4 欧拉定理欧拉定理 费马小定理费马小定理() 1( ,)1,1 (m2.4. (d).1ommuleraamEm 设设 是是大大于于 的的整整定定理理 数数 则则定定理理， ()1 2()1 2()(mod).mmmar rrr rrm 即即 ()mm 因因等等于于模模 的的简简化化剩剩余余系系所所含含分分析析: :元元个个数数, ,12()12()

49、,mmr rrmar arar又又若若是是模模 的的简简化化剩剩余余系系 则则(mod).ijmarrm 也也是是模模 的的简简化化剩剩余余系系, ,所所以以于于是是 12()1 2()()()()(mod)mmarararr rrm 70()1 2()1 2() (mod)mmmar rrr rrm 即即 (mod)ijarrm 12(), , , mrrrm 证证 取取为为模模 的的一一个个简简化化剩剩余余系系 , ,12()( ,)1,ma mar ararm 则则因因于于是是也也是是模模 的的简简化化剩剩余余系系 因因此此, , 12()1 2()()()() (mod)mmarara

50、rr rrm 所所以以 ( ,)1, 1,2, ()ir mim 又又因因 1 2()(,)1mr rrm 所所以以 ()1 (mod).mam 故故 71 7,2,(2,7)1, ( )6.17ma 设设例例有有 12,24,36,41,53,65 (mod7)22222271,2,3,4,5,6,取取模模 的的最最小小非非负负简简化化剩剩余余系系则则有有 (1)(2)(3)(4)(5)(6)2222426 1 3 5 (m2od )27 于于是是 6(1 2 3 4 5 6)1 2 3 4 5 6 (mod72)即即 621 (mod7) 所所以以 6(2641 (mod7)72 830,

51、7,(7,30)1, (30)8,71 (m)2od30ma 设设因因所所以以例例 1011,2,(2,11)1, (11)10,21 (mod 1)31ma 设设例例因因所所以以 2223,23 |,( ,23)1, (23)22,1 (mod23)4maaa 设设若若则则所所以以例例 1122 (mod)11 23(mo 2 )3daa m为素数时，有为素数时，有Fermat定理定理73() (mod)2.4.2ppaaaFermatp 设设 是是素素数数 则则对对任任何何整整数数 , ,有有 定定理理 定定 理理 , , ,| ,( , )1.pap aa p 证证 因因 是是素素数数

52、则则对对任任何何整整数数有有或或 , ,1( )1, 1 (mod)pppap 又又于于是是| , (mod).pp aaap 若若显显然然有有 (mod)paap()( , )1,1 (mod)pa pap 若若则则由由欧欧拉拉定定理理 74 () RSA , ( ,)1,1( ),( , ( )15,1( ),1 (mod ( )(mod ),1,(mod ).edp qnpqa pqeenenddnednacncncan 设设是是两两个个不不同同的的奇奇素素数数如如果果整整数数 满满足足那那么么存存在在整整数数使使得得而而且且对对于于整整数数有有 例例 1 (mod ( )edn ( ,

53、 ( )1,1( ),enddn证证 因因则则存存在在整整数数使使得得由定理由定理2.3.475,1( ).kedkn 于于是是存存在在正正整整数数使使得得 ( ,)1,( , )1,a pqa pEuler因因所所以以由由定定理理 ()1 (mod)pap () ( )1 (mod2 14).kpqap 节节定定理理（） ( )1 (mod)knap 1( )(mod)knaap 于于是是 (mod)edaap 即即 (mod )edaaq 同同理理 (mod )edaan 于于是是因因p,q=pq=n (mod , )(2.112)edaap q 节节定定理理76 ,(mod ),ecan

54、 因因此此 由由 可可得得 ()(mod )dededcaaan ,(1)3!1 (mo)d)(Wipspl onp 设设 是是定定个个素素理理一一数数 则则定定理理,1,aap数数使使得得 2(21)!1 (mod2),.p 证证 （）时时, ,纳纳法法结结论论成成立立归归 3,1,paap设设则则对对于于每每个个存存在在唯唯一一的的整整 1 (mod)aap 由定理由定理2.3.477 2(d1 mo)apaa 于于是是 ,11.aap这这时时或或2,3,2paa 把把中中的的 与与配配对对, ,有有2,2,. aapaa 因因此此当当 与与取取中中的的数数时时32()()(2 32)paapaaaaaa 对对的的所所有有可可能能情情况况对对（） 1 (mod)aap 因因 2 321 (mod)pp所所以以 (1)!1 (1)pp故故 1 (mod)p 78 2 91813 6