信安第二章第4节

1、12.4 2.4 欧拉定理欧拉定理 费马小定理费马小定理() 1( ,)1,1 (mod)(.mmula mermea 设设是是大大于于 的的整整 定定理理则则定定理理数数， 1 1 ()1 2()1 2()(mod).mmmar rrr rrm 即即 ()mm 因因等等于于模模 的的简简化化剩剩余余系系所所含含分分析析: :元元个个数数, ,12()12(),mmr rrmar arar又又若若是是模模 的的简简化化剩剩余余系系 则则(mod).ijmarrm 也也是是模模 的的简简化化剩剩余余系系, ,所所以以于于是是 12()1 2()()()()(mod)mmarararr rrm 2

2、()1 2()1 2() (mod)mmmar rrr rrm 即即 (mod)ijarrm 12(), , , mrrrm 证证 取取为为模模 的的一一个个简简化化剩剩余余系系 , ,12()( ,)1,ma mar ararm 则则因因于于是是也也是是模模 的的简简化化剩剩余余系系 因因此此, , 12()1 2()()()() (mod)mmarararr rrm 所所以以 ( ,)1, 1,2, ()ir mim 又又因因 1 2()(,)1mr rrm 所所以以 ()1 (mod).mam 故故 3 7,2,(2,7)1, ( )6.17ma 设设例例有有 12,24,36,41,5

3、3,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)4 830,7,(7,30)1, (30)8,71 (m)2od30ma 设设因因所所以以例例 1011,2,(2,11)1, (11)10,21 (mod11)ma 设设例例3 3因因所所以以 2223,23 |,( ,23)1, (23)22,1 (m

4、od)423maaa 设设例例则则所所以以 1122 (mod)11 23(mo 2 )3daa 5 (mod)()2ppfermaaapat 设设 是是素素数数 则则对对任任何何整整数数 , ,有有 定定定定 理理 理理 , , ,| ,( , )1.pap aa p 证证 因因 是是素素数数 则则对对任任何何整整数数有有或或 , ,1( )1, 1 (mod)pppap 又又于于是是| , (mod).pp aaap 若若显显然然有有 (mod)paap()( , )1,1 (mod)pa pap 若若则则由由欧欧拉拉定定理理 6 , ( ,)1,1( ),( , ( )1,1( ),1

5、(mod ( )(mod ),1,(mod ).5edp qnpqa pqeenenddnednacncncan 设设是是两两个个不不同同的的奇奇素素数数如如果果整整数数 满满足足那那么么存存在在整整数数 使使得得而而且且对对于于整整数数有有 例例 1 (mod ( )edn ( , ( )1,1( ),enddn证证 因因则则存存在在整整数数使使得得由由2.32.3定理定理4 47,1( ).kedkn 于于是是存存在在正正整整数数使使得得 ( ,)1,( , )1,a pqa peuler因因所所以以由由定定理理 ()1 (mod)pap () ( )1 (mod)kpqap ( )1 (

6、mod)knap 1( )(mod)knaap 于于是是 (mod)edaap 即即 (mod )edaaq 同同理理 (mod )edaan 于于是是因因p,q=pq=n (mod , )edaap q 8 ,(mod ),ecan 因因此此 由由 可可得得 ()(mod )dededcaaan ,(1)3!1 (mo)d)(wipspl onp 设设 是是定定个个素素理理一一数数 则则定定理理,1,aap数数使使得得 2(21)!1 (mod2),.p 证证 时时, ,结结论论成成立立 3,1,paap设设则则对对于于每每个个存存在在唯唯一一的的整整 1 (mod)aap 由由2.32.3

7、定理定理4 49 21 (mod)aaap于于是是 ,11.aap这这时时或或2,3,2paa 把把中中的的 与与配配对对, ,有有2,2,.aapaa因因此此当当 与与取取中中的的数数时时32()()()2 32paaaaaap 对对 1 (mod)aap 因因 2 321 (mod)pp所所以以 (1)!1 (1)pp故故 1 (mod)p 10 2 91813 61814 135215 73518 15120110 12120111 141541(mod17), , , , , , , , , 167,p 例例设设有有1 16161(mod17) 而而 ( 1) 1 1 1 1 1 1

8、1 因因此此(1 16)(2 9)(3 6)(4 13)(5 7)(8 15)(10 12)(11 14) 1 (mod17) 16!1 (mod17) 即即1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161152p 若若为为素素数数，则则（p-3p-3）!+10(mo.!+10(mo.例例7 7dp)dp) 402402求求出出243243的的最最后后三三例例8 8位位数数字字。7 77 77 7求求7 7 的的例例9 9末末位位数数字字。777777求求777777的的练练习习末末位位数数字字。 pppppp证证明明当当p p为为素素数数时时，且且a,bza,b

9、z，则则有有（a+ba+b）a +b (moa +b (mo例例1010dp)dp)。(mod1000)a 100n+1100n+1证证明明若若（a,10a,10）=1=1练练, ,则则a a习习125628(1237134)111 例例1 1求求被被除除2 2的的余余数数. . 21237111150 解解由由 56561237150 (mod111)35014 (mod111) 又又因因 ，28950(14) 50 (mod111)31480 (mod111) 又又因因 38068 (mod111), 而而2839 50(50 ) 50 (mod111) 931480 (mod111)28

10、506850 (mod111)所所以以1237150 (mod111)1370.故故所所求求余余数数是是562507016 (mod111)所所以以 5656123715016 (mod111)于于是是 56123713450 (mod111)562828(1237134)5070 (mod111)6850 70 (mod111)又又285070 (mod111)1437 73 12?求求（mod37mod37例例 1 1. .1 17373） 661110(mod42);0(mod7)(,)7|nnmnabnabnnaam nza 7 7、若若 与与 均均不不能能被被素素数数整整除除，则则可

11、可被被整整除除。2 2、对对于于任任意意整整数数n,n,都都有有n n3 3、求求证证：当当思思考考题题且且仅仅当当时时成成立立。 15本本章章主主要要内内容容同同余余费费马马定定理理剩剩余余类类基基本本性性质质完完全全剩剩余余系系简简化化剩剩余余系系欧欧拉拉定定理理简简化化剩剩余余类类欧欧拉拉函函数数及及其其计计算算方方法法1623813pp 半半期期试试题题第第1 1题题1010分分，2-72-7题题各各1515分分。、为为素素数数，求求证证不不能能为为素素数数。、问问的的最最后后两两位位数数？、用用同同余余的的方方法法证证明明：是是否否存存在在五五个个连连续续自自然然数数，将将得得前前四四个个数数的的平平方方和和等等于于第第五五个个数数的的平平方方。123412341 12123452123451026(mod817)20!x 4 4、解解同同余余式式方方程程5895895 5、求求的的标