信安第二章第4節(jié)

1、12.4 2.4 歐拉定理歐拉定理 費(fèi)馬小定理費(fèi)馬小定理() 1( ,)1,1 (mod)(.mmula mermea 設(shè)設(shè)是是大大于于 的的整整 定定理理則則定定理理數(shù)數(shù)， 1 1 ()1 2()1 2()(mod).mmmar rrr rrm 即即 ()mm 因因等等于于模模 的的簡簡化化剩剩余余系系所所含含分分析析: :元元個個數(shù)數(shù), ,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 設(shè)設(shè)例例有有 12,24,36,41,5

3、3,65 (mod7)22222271,2,3,4,5,6,取取模模 的的最最小小非非負(fù)負(fù)簡簡化化剩剩余余系系則則有有 (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 設(shè)設(shè)因因所所以以例例 1011,2,(2,11)1, (11)10,21 (mod11)ma 設(shè)設(shè)例例3 3因因所所以以 2223,23 |,( ,23)1, (23)22,1 (m

4、od)423maaa 設(shè)設(shè)例例則則所所以以 1122 (mod)11 23(mo 2 )3daa 5 (mod)()2ppfermaaapat 設(shè)設(shè) 是是素素數(shù)數(shù) 則則對對任任何何整整數(shù)數(shù) , ,有有 定定定定 理理 理理 , , ,| ,( , )1.pap aa p 證證 因因 是是素素數(shù)數(shù) 則則對對任任何何整整數(shù)數(shù)有有或或 , ,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 設(shè)設(shè)是是兩兩個個不不同同的的奇奇素素數(shù)數(shù)如如果果整整數(shù)數(shù) 滿滿足足那那么么存存在在整整數(shù)數(shù) 使使得得而而且且對對于于整整數(shù)數(shù)有有 例例 1 (mod ( )edn ( , ( )1,1( ),enddn證證 因因則則存存在在整整數(shù)數(shù)使使得得由由2.32.3定理定理4 47,1( ).kedkn 于于是是存存在在正正整整數(shù)數(shù)使使得得 ( ,)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 設(shè)設(shè) 是是定定個個素素理理一一數(shù)數(shù) 則則定定理理,1,aap數(shù)數(shù)使使得得 2(21)!1 (mod2),.p 證證 時時, ,結(jié)結(jié)論論成成立立 3,1,paap設(shè)設(shè)則則對對于于每每個個存存在在唯唯一一的的整整 1 (mod)aap 由由2.32.3

7、定理定理4 49 21 (mod)aaap于于是是 ,11.aap這這時時或或2,3,2paa 把把中中的的 與與配配對對, ,有有2,2,.aapaa因因此此當(dāng)當(dāng) 與與取取中中的的數(shù)數(shù)時時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 例例設(shè)設(shè)有有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 若若為為素素數(shù)數(shù)，則則（p-3p-3）!+10(mo.!+10(mo.例例7 7dp)dp) 402402求求出出243243的的最最后后三三例例8 8位位數(shù)數(shù)字字。7 77 77 7求求7 7 的的例例9 9末末位位數(shù)數(shù)字字。777777求求777777的的練練習(xí)習(xí)末末位位數(shù)數(shù)字字。 pppppp證證明明當(dāng)當(dāng)p p為為素素數(shù)數(shù)時時，且且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習(xí)習(xí)125628(1237134)111 例例1 1求求被被除除2 2的的余余數(shù)數(shù). . 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.故故所所求求余余數(shù)數(shù)是是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、若若 與與 均均不不能能被被素素數(shù)數(shù)整整除除，則則可

11、可被被整整除除。2 2、對對于于任任意意整整數(shù)數(shù)n,n,都都有有n n3 3、求求證證：當(dāng)當(dāng)思思考考題題且且僅僅當(dāng)當(dāng)時時成成立立。 15本本章章主主要要內(nèi)內(nèi)容容同同余余費(fèi)費(fèi)馬馬定定理理剩剩余余類類基基本本性性質(zhì)質(zhì)完完全全剩剩余余系系簡簡化化剩剩余余系系歐歐拉拉定定理理簡簡化化剩剩余余類類歐歐拉拉函函數(shù)數(shù)及及其其計(jì)計(jì)算算方方法法1623813pp 半半期期試試題題第第1 1題題1010分分，2-72-7題題各各1515分分。、為為素素數(shù)數(shù)，求求證證不不能能為為素素數(shù)數(shù)。、問問的的最最后后兩兩位位數(shù)數(shù)？、用用同同余余的的方方法法證證明明：是是否否存存在在五五個個連連續(xù)續(xù)自自然然數(shù)數(shù)，將將得得前前四四個個數(shù)數(shù)的的平平方方和和等等于于第第五五個個數(shù)數(shù)的的平平方方。123412341 12123452123451026(mod817)20!x 4 4、解解同同余余式式方方程程5895895 5、求求的的標(biāo)