版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、 初等數(shù)論 - 第三章(1) 同余、剩余類n同余:基本概念、性質(zhì)、應(yīng)用同余:基本概念、性質(zhì)、應(yīng)用n剩余系、完全剩余系:定義、性質(zhì)剩余系、完全剩余系:定義、性質(zhì)n簡化剩余系、歐拉函數(shù):定義、算法簡化剩余系、歐拉函數(shù):定義、算法n歐拉定理、費馬定理:內(nèi)容、證明、應(yīng)用歐拉定理、費馬定理:內(nèi)容、證明、應(yīng)用nRSARSA體制:算法、正確性證明體制:算法、正確性證明本章基本內(nèi)容本章基本內(nèi)容2n本章所介紹的同余這一特殊語言在數(shù)論中極為有本章所介紹的同余這一特殊語言在數(shù)論中極為有用,它是由歷史上最著名的數(shù)學(xué)家之一卡爾用,它是由歷史上最著名的數(shù)學(xué)家之一卡爾弗弗里德里希里德里希高斯(高斯(Kar Friedric
2、h GaussKar Friedrich Gauss)于)于1919世紀(jì)世紀(jì)初提出的初提出的. .n同余的語言使得人們能用類似處理等式的方式來同余的語言使得人們能用類似處理等式的方式來處理整除關(guān)系處理整除關(guān)系. . 在引入同余之前,人們研究整除關(guān)在引入同余之前,人們研究整除關(guān)系所用的記號笨拙而且難用系所用的記號笨拙而且難用. . 而引入方便的記號而引入方便的記號對加速數(shù)論的發(fā)展起到了幫助作用對加速數(shù)論的發(fā)展起到了幫助作用. .31 同余的概念及其基本性質(zhì)同余的概念及其基本性質(zhì)n今天(今天(20152015年年4 4月月8 8日)是星期三,問明年的日)是星期三,問明年的今天是星期幾?(今天是星期
3、幾?(20162016年年4 4月月8 8日)日)n明年的今天(明年的今天(20162016年年4 4月月8 8日)是星期五日)是星期五4,.,(mod).,(mod).9(mo 5),dmmaba bmabma bmabm 定定義義 給給定定一一個個正正整整數(shù)數(shù)把把它它叫叫做做如如果果用用去去除除任任意意兩兩個個整整數(shù)數(shù) 與與 所所得得的的余余數(shù)數(shù)相相同同, , 我我們們就就說說對對模模記記作作 如如果果余余數(shù)數(shù)不不同同 我我們們就就說說對對模模記記作作 例例 7 72 2 ( (m mo od d 5 5) ), ,7 71 12 2 ( (m mo od d 5 5) ), ,7 7模模
4、同同余余不不同同余余5n鐘表對于小時是模鐘表對于小時是模1212或或2424的,對于分鐘和秒是模的,對于分鐘和秒是模6060的的n日歷對于星期是模日歷對于星期是模7 7的,對于月份是模的,對于月份是模1212的的n電水表通常是模電水表通常是模10001000的的n里程表通常是模里程表通常是模100000100000的的 同余在日常生活中的應(yīng)用同余在日常生活中的應(yīng)用60(mod),0(mod).1,1(mod).,0, 1, 2,.m aamaaaabmbmbkm k 可可記記為為 所所以以, ,所所有有的的偶偶數(shù)數(shù)可可以以表表為為 2 2 由由于于奇奇數(shù)數(shù)滿滿足足2 2所所以以, ,所所有有的
5、的奇奇數(shù)數(shù)可可以以表表為為 2 2對對給給定定的的整整數(shù)數(shù) 和和模模所所有有同同余余于于模模的的數(shù)數(shù)就就是是算算術(shù)術(shù)數(shù)數(shù)列列7(mod),ii(mod)(mod),iii (mod),(mod)(mod0,()().aamabmbamabm aam abm bam ab mm bcmacbcm abbcamc同同余余是是一一種種等等價價關(guān)關(guān)系系, , 即即有有 自自反反性性 對對稱稱性性 傳傳遞遞性性 證證由由及及 以以i811221212121212121212,0,0,(mod),() .,1,()(),. , aq mr bq mrrmrmabmrrabqq mm abm m qqrrm
6、 rrrrmra bmm abrm aba batmbmt 證證 設(shè)設(shè)若若則則, ,因因此此反反之之,若若則則, ,因因此此, ,. .但但故故定定理理1 1表表明明同同余余又又可可定定義義定定理理 整整數(shù)數(shù)對對模模同同余余的的充充要要條條件件是是, ,如如下下: :若若則則對對模模即即是是整整數(shù)數(shù). .同同余余. .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).kk
8、kkkkkkiikkiinnnnnnnnABmxym 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 證證 由由定定理理 但但故故即即若若 則則 則則 若若 是是及及的的任任一一正正公公因因數(shù)數(shù) 則則 1312121,1,2, ,3 ,(mod
9、),1,2, ,(mod ,).(mod),0,(mod). (mod),( ,)( ,1 , )ikikabmikabm mmabm d m dabdabma mb mdmm ab ikm mmaba bd 證證 由由定定理理 再再由由第第一一章章定定理理, ,即即得得故故由由 若若 則則 若若 則則 若若 則則因因而而若若定定理理 即即證證能能整整除除及及二二得得. .數(shù)數(shù)之之一一, ,則則, a b必必能能整整除除中中另另一一個個. .14(),().( ,) ( ,)/ ( ,),(mod)(7)(mod/ ( ,).( ,)1(mod),./ ( ,)().( ,)cacbmabmc
10、 mc mabm c abmcabc mc mmc m cc mmabc mmc性性質(zhì)質(zhì) 同同余余式式 等等價價于于 特特別別地地, ,當(dāng)當(dāng)時時, ,同同余余式式(7)(7)等等價價于于 即即同同余余式式兩兩邊邊可可約約去去 證證 同同余余式式(7)(7)即即這這等等價價于于由由定定理理及及()=1()=1知知, ,這這等等價價于于1500001101,1.(m1,( ,)1,1(mod),(mod).od)ma mccamcamabmx yaxmycxama 證證 由由定定理理知知, , 存存在在使使得得取取 既既滿滿足足要要求求. . 由由此此提提供供一一性性質(zhì)質(zhì)若若則則存存在在使使得得
11、我我們們種種求求 有有效效的的方方法法, ,這這是是EuclEucl把把稱稱idid為為是是對對模模的的逆逆,記記作作 算算法法的的又又一一或或重重要要應(yīng)應(yīng)用用. .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、模模的的逆逆 不不是是惟惟一一的的. .當(dāng)當(dāng) 是是 對對模模的的逆逆時時, ,任任一一 也也一一定定是是 對對模模的的逆逆 由由性性質(zhì)質(zhì)知知, 對對模模的的任任意意兩兩個個逆逆必必有有 此此外外, ,顯顯見見( (, ,) )= =1 1及及( ( 18110100.1010,010(mod 3).3.9nnnninnniiaaaaaaaaaaaaaa 應(yīng)應(yīng)用用 檢檢查查因因數(shù)數(shù)的的一一些些方方法法 A. A. 一一整整數(shù)數(shù)能能被被3(9)3(9)整整除除的的必必要要且且充充分分條條件件是是它它的的十十進(jìn)進(jìn)位位數(shù)數(shù)碼碼的的和和能能被被3(9)3(9)整整除除 證證 顯顯然然我我們們只只須須討討
13、論論任任一一整整數(shù)數(shù) 就就夠夠了了. .按按照照通通常常方方法法, ,把把寫寫成成十十進(jìn)進(jìn)位位數(shù)數(shù)的的形形式式; ;即即因因101(mod 3),101(mod 3),故故定定理理得得由由性性質(zhì)質(zhì)知知3 3 當(dāng)當(dāng)且且僅僅當(dāng)當(dāng) 同同法法可可得得 當(dāng)當(dāng)且且09.niia僅僅當(dāng)當(dāng) 1911002130010001000,010007(11 13)( 1)-7(1113)( 1)7(11 13)nnnniniiiniiiaaaaaaaaaaaa 應(yīng)應(yīng)用用 檢檢查查因因數(shù)數(shù)的的一一些些方方法法 B. B. 設(shè)設(shè)正正整整數(shù)數(shù)則則7(7(或或11,11,或或13)13)整整除除 的的必必要要且且充充分分的的
14、條條件件是是或或或或整整除除(+)-(+)=(+)-(+)= 證證 因因為為10001000與與 1 1對對模模7(7(或或11,11,或或13)13)同同余余, ,故故由由定定理理知知或或或或與與對對模?;蚧蚧蚧蛲嘤? .07(11 13)7(11 13)( 1).niiiaa由由性性質(zhì)質(zhì), 或或或或整整除除當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)或或或或整整除除2000105874192,5874192363,9,3,9435693,435693303,39637693,637 1000693,69363756niiniiniiniiaaA aaaAaaaaaa 例例1 1 若若則則能能被被整整除除. .故故
15、由由能能被被整整除除. . 例例2 2 若若則則能能被被 整整除除. .故故由由是是 的的因因數(shù)數(shù). .但但不不能能被被 整整除除, ,故故9 9不不是是 的的因因數(shù)數(shù) 例例3 3 若若則則能能被被7 7整整除除而而不不.aa能能1111與與1313整整除除. .故故由由B,7B,7是是 的的因因數(shù)數(shù), ,但但11,1311,13不不是是 的的因因數(shù)數(shù)21110110-1-10=00=0,1010,0101010,01010 +10 +,010 (mod nnnnimmmmjllllknmlijkijka bPaaaaabbbbbPccccabc II II 棄棄九九法法( (驗驗算算整整數(shù)數(shù)
16、計計算算結(jié)結(jié)果果的的方方法法) ) 假假設(shè)設(shè)我我們們由由普普通通乘乘法法的的運運算算方方法法求求出出整整數(shù)數(shù)的的乘乘積積是是 , ,并并令令,我我們們說說:如如果果=00=0=00=09),.2, (mod 9), (mod 9). (mod 9), (mod 9).nmijijlnmlkijkkijkababPcabcabPabP那那么么所所求求得得的的乘乘積積是是錯錯誤誤的的 因因為為定定理理 及及性性質(zhì)質(zhì)若若則則故故不不是是 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寫寫成成十十進(jìn)進(jìn)位位數(shù)數(shù)時時的的個個位位數(shù)數(shù). . 解解 要要求求 滿滿足足 3 3顯顯然然有有,33,33進(jìn)進(jìn)而而有有3 3因因此此,333333所所以以個個位位數(shù)數(shù)是是9.9.24406406244812(mod 100),099.1(mod 4),1(mod 5).41(mod 2
18、5),.816(mod 25),3611(mod 25),669(mod 2dbbbdd 例例 求求3 3寫寫成成十十進(jìn)進(jìn)位位數(shù)數(shù)時時的的最最后后兩兩位位數(shù)數(shù). . 解解 只只要要求求出出 滿滿足足 3 3注注意意到到100=4 25,(4,25)=1,100=4 25,(4,25)=1,顯顯然然有有,33,33注注意意到到 是是最最小小的的方方次次, ,由由第第一一章章 4 4例例5 5知知, ,使使3 3成成立立的的必必有有4 4因因此此計計算算33333 316202020400406400665),544(mod 25),241(mod 25),1(mod 4),IX1(mod100)
19、,1(mod100).29(mod 100). 3 33 3由由此此及及3 3從從性性質(zhì)質(zhì)推推出出3333因因此此33333333所所以以個個位位數(shù)數(shù)是是9,9,十十位位數(shù)數(shù)是是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 mod 23. 解解 首首先先找找到到一一個個整整數(shù)數(shù)滿滿足足6 6
20、由由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.先先將將指指數(shù)數(shù)644644表表示示成成二二進(jìn)進(jìn)制制形形式式 = = 2. 2.然然后后, ,
21、用用逐逐個個平平方方及及模模645645約約化化來來計計算算的的最最小小正正剩剩余余. .求求2 2模模指指數(shù)數(shù)運運算算: :6 6 模模 4545644644512 128 45121284641284mod 645).64522222256 391 1616015361(mod 645)2256(mod 645);2391(mod 645);216(mod 645)3.3.現(xiàn)現(xiàn)在在用用2 2的的合合適適的的方方冪冪的的最最小小正正剩剩余余的的乘乘積積來來計計算算2 2模模2711022422,.,.kjNkkjbmb mNNNa aa ab b bbmajbmm 即即計計算算模模的的一一般
22、般過過程程, ,其其中中和和是是正正整整數(shù)數(shù). .首首先先, ,將將 用用二二進(jìn)進(jìn)制制記記號號表表示示成成然然后后, ,用用逐逐個個平平方方及及模模約約化化求求出出模模的的最最小小正正剩剩余余. .最最后后, ,取取=1=1的的 所所對對應(yīng)應(yīng)的的模模的的最最小小正正剩剩余余的的乘乘積積, ,再再模模約約指指數(shù)數(shù)運運算算化化即即可可模模282222422122222,.loglog,22loglogloglogkNmNNkkmNNmb mNbmbmObmmb b bbmNOmON 定定理理 設(shè)設(shè)和和 是是正正整整數(shù)數(shù), ,且且則則計計算算模模的的最最小小正正剩剩余余要要用用次次位位運運算算. .
23、 證證明明:用用上上面面所所描描述述的的算算法法來來求求模模的的最最小小正正剩剩余余. .首首先先, ,用用逐逐個個平平方方及及模模約約化化求求出出模模的的最最小小正正剩剩余余, ,其其中中. .這這總總共共需需要要比比特特的的運運算算, ,因因為為要要做做次次模模平平方方, ,每每次次平平方方需需要要次次位位運運算算. .然然后后, ,取取 的的二二進(jìn)進(jìn)制制2222222222mloglog,loglog.loglogjmNNmmNbOOO表表示示中中為為1 1的的數(shù)數(shù)字字對對應(yīng)應(yīng)的的的的最最小小正正剩剩余余的的乘乘積積, ,在在每每次次乘乘法法之之后后模模約約化化. .這這也也需需要要次次
24、位位運運算算因因為為至至多多有有次次乘乘法法, ,而而每每次次乘乘法法需需要要次次位位運運算算因因此此總總共共需需要要次次位位運運算算. .29011 1,(0,1,1) (i) (ii)mrmmK KKK rmqmrm 定定理理若若是是一一個個給給定定的的正正整整數(shù)數(shù) 則則全全部部整整數(shù)數(shù)可可分分成成個個集集合合, ,記記作作其其中中是是由由一一切切形形如如的的整整數(shù)數(shù)所所組組成成的的. .這這些些集集合合具具有有下下列列性性質(zhì)質(zhì):每每一一整整數(shù)數(shù)必必包包括括在在而而且且僅僅在在上上述述的的一一個個集集合合里里面面兩兩個個整整數(shù)數(shù)同同在在一一個個集集合合的的充充分分與與必必要要條條件件是是這
25、這兩兩個個整整數(shù)數(shù)對對模模同同余余2 2 剩余類及完全剩余系剩余類及完全剩余系30112(i), 14,0.,(mod),.aaaararrraaa mrrmaKraaKa bKaq mrbq mrabma bK 證證設(shè)設(shè) 是是任任一一整整數(shù)數(shù) 由由第第一一章章定定理理 即即得得故故在在內(nèi)內(nèi). .又又由由同同一一定定理理知知道道 是是由由 惟惟一一確確定定的的因因此此 只只能能在在內(nèi)內(nèi). . (ii) (ii)設(shè)設(shè)是是兩兩個個整整數(shù)數(shù), ,并并且且都都在在內(nèi)內(nèi), ,則則故故則則由由同同余余的的定定義義即即知知同同在在某某一一個個內(nèi)內(nèi)31011011011 1,. . mmmK KKma aam
26、a aammmm 定定義義定定理理中中的的叫叫做做模模的的剩剩余余類類一一個個剩剩余余類類中中任任一一數(shù)數(shù)叫叫做做它它同同類類的的數(shù)數(shù)的的剩剩余余. .若若是是個個整整數(shù)數(shù) 并并且且其其中中任任何何兩兩數(shù)數(shù)都都不不同同在在一一個個剩剩余余類類里里, ,則則叫叫做做模模的的一一個個完完全全剩剩余余系系推推論論個個整整數(shù)數(shù)作作成成模模的的一一個個完完全全剩剩余余系系的的充充分分與與必必要要條條件件是是兩兩兩兩對對模模不不同同余余321 0,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,
27、1,0,12ammmamammmmmammmmmmmmmmmmm 例例 序序列列 都都是是模模的的完完全全剩剩余余類類. .當(dāng)當(dāng)是是雙雙數(shù)數(shù)時時 序序列列- -都都是是模模的的完完全全剩剩余余類類. .當(dāng)當(dāng)是是單單數(shù)數(shù)時時 序序列列- -1,; (6)2mm都都是是模模的的完完全全剩剩余余類類. .330101( ,)1,mmma mbxmaxbmaamaabaabm 定定理理2 2 設(shè)設(shè)是是正正整整數(shù)數(shù), , 是是任任意意整整數(shù)數(shù)若若 通通過過模模的的一一個個完完全全剩剩余余系系, ,則則也也通通過過模模的的一一個個完完全全剩剩余余系系, ,也也就就是是說說, ,若若,是是模模的的一一個個完完全全剩剩余余系系, ,則則,也也是是模模的的完完全全剩剩余余系系. .3401011 1(mod),().1(mod). ( ,)1(mod). ,mijijijmaabaaba
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五版城市住宅抵押借款合同示范4篇
- 二零二五年度農(nóng)產(chǎn)品電商平臺農(nóng)產(chǎn)品質(zhì)量保險合同4篇
- 二零二五年度滅鼠防治項目監(jiān)理合同3篇
- 2025年度紡織面料品牌形象設(shè)計與推廣合同4篇
- 2025年度自然人與音樂制作人創(chuàng)作合同3篇
- 二零二五年度出境領(lǐng)隊培訓(xùn)基地建設(shè)合同4篇
- 2025物業(yè)保潔與緊急維修值班服務(wù)一體化項目合同9篇
- 2025年度智能停車設(shè)施門面房產(chǎn)權(quán)轉(zhuǎn)讓合同4篇
- 2025年度個人與公司租賃合同糾紛處理條款4篇
- 二零二五年度啤酒品牌市場推廣代理合同3篇
- 中國人民銀行清算總中心直屬企業(yè)2023年招聘筆試上岸歷年典型考題與考點剖析附帶答案詳解
- 2024年湖南高速鐵路職業(yè)技術(shù)學(xué)院單招職業(yè)技能測試題庫及答案解析
- (正式版)SJT 11449-2024 集中空調(diào)電子計費信息系統(tǒng)工程技術(shù)規(guī)范
- 廣州綠色金融發(fā)展現(xiàn)狀及對策的研究
- 人教版四年級上冊加減乘除四則混合運算300題及答案
- 合成生物學(xué)技術(shù)在生物制藥中的應(yīng)用
- 消化系統(tǒng)疾病的負(fù)性情緒與心理護(hù)理
- 高考語文文學(xué)類閱讀分類訓(xùn)練:戲劇類(含答案)
- 協(xié)會監(jiān)事會工作報告大全(12篇)
- WS-T 813-2023 手術(shù)部位標(biāo)識標(biāo)準(zhǔn)
- 同意更改小孩名字協(xié)議書
評論
0/150
提交評論