信息安全數(shù)學(xué)基礎(chǔ)(第一章)2014-2015下

1、1信息安全數(shù)學(xué)基礎(chǔ)信息安全數(shù)學(xué)基礎(chǔ) 王騫王騫 武漢大學(xué)計算機學(xué)院武漢大學(xué)計算機學(xué)院2一、信息安全數(shù)學(xué)基礎(chǔ)的內(nèi)容一、信息安全數(shù)學(xué)基礎(chǔ)的內(nèi)容 內(nèi)容： 初等數(shù)論、近世（抽象）代數(shù)、橢圓曲線 方式：課堂教學(xué)為主 目的：了解和掌握數(shù)論和代數(shù)的基本知識，包括整數(shù)整數(shù) 的可除性的可除性 、同余、同余式、二次同余式與平方、同余、同余式、二次同余式與平方 剩余剩余 、原根、原根、群、環(huán)、域群、環(huán)、域和和橢圓曲線橢圓曲線等等二、教學(xué)方式和目的二、教學(xué)方式和目的3三、數(shù)論和代數(shù)在信息安全中的作用三、數(shù)論和代數(shù)在信息安全中的作用 例：公鑰密碼學(xué)（Public-key cryptography）所基于的三個難解數(shù)學(xué)問題

2、: 1. 大因數(shù)分解問題（RSA加密(簽名) 安全基礎(chǔ)） 2. 離散對數(shù)問題 3. 橢圓曲線離散對數(shù)問題 都涉及數(shù)論、代數(shù)和橢圓曲線論中的部分知識。 信息安全數(shù)學(xué)基礎(chǔ) - 密碼學(xué)基礎(chǔ) - 網(wǎng)絡(luò)（信息）安全基礎(chǔ)4三、課程考核三、課程考核 閉卷考試+作業(yè)四、成績計算四、成績計算 平時作業(yè)30% + 考試70% 五、教材和參考書目五、教材和參考書目1信息安全數(shù)學(xué)基礎(chǔ)，清華大學(xué)出版社，陳恭亮信息安全數(shù)學(xué)基礎(chǔ)，清華大學(xué)出版社，陳恭亮2信息安全數(shù)學(xué)基礎(chǔ)清華大學(xué)出版社，覃中平、張 煥國看書時注意書中的書寫錯誤?？磿鴷r注意書中的書寫錯誤。5第一章第一章 整數(shù)的可除性整數(shù)的可除性要求：要求：掌握整除、素數(shù)、最大

3、公因數(shù)等的定義，熟練運用歐幾里得除法和廣義歐幾里得除法。 61.1 1.1 整除的概念整除的概念 歐幾里得除法歐幾里得除法一、整除基本概念及性質(zhì)一、整除基本概念及性質(zhì) 1.1,.10|a bbqabqbaabb a 設(shè)設(shè)是是任任意意兩兩個個整整數(shù)數(shù), ,其其中中如如果果存存在在一一個個整整數(shù)數(shù) 使使得得等等式式成成立立, ,則則稱稱或或者者 被被 整整除除, ,記記作作除除 義義整整 定定如如果果 不不能能整整除除則則記記作作,|.baba 因因數(shù)數(shù)如如果果則則 叫叫做做 的的而而 叫叫做做 的的倍倍數(shù)數(shù)| ,.b abaab寫寫成成或或/.aa bb此此時時 可可q7 當(dāng)當(dāng) 遍遍歷歷整整數(shù)數(shù)

4、 的的所所有有因因數(shù)數(shù)時時也也遍遍歷歷整整數(shù)數(shù) 的的所所有有因因數(shù)數(shù)(2), /.baa ba 當(dāng)當(dāng) 遍遍歷歷整整數(shù)數(shù) 的的所所有有因因數(shù)數(shù)時時也也遍遍歷歷整整數(shù)數(shù) 的的因因注注所所有有數(shù)數(shù)(1),:.baba 對對任任何何整整數(shù)數(shù)有有(5)0,| .aa a 對對任任何何整整數(shù)數(shù)有有(3)0,| 0.bb 對對任任何何整整數(shù)數(shù)有有1 1| |(4),.bb 若若則則(6)| ,|(),()|().b ababa 8 1,0,0| , | ,| .1.1a bcc b b ac a 設(shè)設(shè)是是三三個個整整數(shù)數(shù). .若若則則定定理理12, | .q qc a因因是是整整數(shù)數(shù) 所所以以12|c bb

5、 aqq證證 設(shè)設(shè)，則則存存在在整整數(shù)數(shù) ， ，使使得得12bcqabq ，于于是是有有21212()()abqcq qc q q 9 1.1.2, ,0| , | ,|.a b cc a c bc ab 設(shè)設(shè)是是三三個個整整數(shù)數(shù). .理理若若定定則則1212()abcqcqc qq 12| , | ,c a c bq q證證 因因所所以以存存在在整整數(shù)數(shù)使使得得 12,acqbcq 12,.qqc | ab 因因是是整整數(shù)數(shù) 所所以以10 1.1.3, ,0| , | ,|.a b cc a c bs tc satb 設(shè)設(shè)是是三三個個整整數(shù)數(shù). .若若則則對對 任任意意整整數(shù)數(shù) , , ,

6、,定定理理有有 12121122,0|,(1,2, ),1.1|.4.ninnna aacc ains ssc s as as a 設(shè)設(shè)是是整整數(shù)數(shù). .若若則則對對任任意意整整數(shù)數(shù), ,有有 定定 理理 1212()()()satbs cqt cqc sqtq 12| , | ,c a c bq q證證 因因所所以以存存在在整整數(shù)數(shù)使使得得 12,acqbcq, ,s t于于是是對對任任意意整整數(shù)數(shù) 12,.sqtqc | satb 因因是是整整數(shù)數(shù) 所所以以11 , ,0,| , | ., ,1,1.1.1.1a b cc a c bs tsatbc 設(shè)設(shè)是是三三個個整整數(shù)數(shù)如如果果存存在

7、在整整數(shù)數(shù)使使得得 則則 例例1.c 故故 | , | ,1,c a c bsatb 證證 因因且且所所以以有有c | satb |1,c12 1.1.5,| , | ,.a ba b b aab 設(shè)設(shè)都都是是非非零零整整數(shù)數(shù), ,若若則則 定定理理 12| , | ,a b b aq q證證 因因所所以以存存在在整整數(shù)數(shù)使使得得 12,abqbaq .ab 從從而而12112()()abqaq qa q q 12,q q于于是是=1=112,q q因因是是整整數(shù)數(shù), ,所所以以121,qq 13二、素數(shù)二、素數(shù)( (質(zhì)數(shù)質(zhì)數(shù)) )及其判別法及其判別法 1.1.2011nnnnn 設(shè)設(shè)整整數(shù)數(shù)

8、， ，如如果果除除了了和和外外， 沒沒有有其其它它因因數(shù)數(shù), ,則則 叫叫做做( (或或素素數(shù)數(shù)質(zhì)質(zhì)數(shù)數(shù)不不可可約約或或) ), ,否否則則 叫叫定定 數(shù)數(shù) 義義做做合合數(shù)數(shù). . 0, 1,:,nnnp 當(dāng)當(dāng)整整數(shù)數(shù)時時和和同同為為素素數(shù)數(shù)或或合合數(shù)數(shù). .因因此此通通常常素素數(shù)數(shù)總總是是指指正正整整數(shù)數(shù) 用用注注表表示示. . 1. 素素數(shù)數(shù)14 1.1.6,1,.npnppn 設(shè)設(shè) 是是一一個個正正合合數(shù)數(shù)是是 的的一一個個大大于于的的最最小小正正因因數(shù)數(shù) 則則 是是素素數(shù)數(shù), ,且且 定定理理 p假假設(shè)設(shè)矛矛盾盾, ,所所以以 是是素素數(shù)數(shù). . , 1,pqqp 證證( () ) 若

9、若 是是合合數(shù)數(shù) 則則存存在在整整數(shù)數(shù)反反證證法法使使得得 | ,| ,p nq n又又于于是是pn這這與與 是是 的的最最小小正正因因數(shù)數(shù)的的 2,.pnpn 因因此此故故 ,1npn因因 是是合合數(shù)數(shù)是是 的的大大于于 的的最最小小正正因因數(shù)數(shù), ,所所以以,n1 1存存在在整整數(shù)數(shù)使使得得 111nnpnpn|.q p15整整數(shù)數(shù)為為素素數(shù)數(shù)的的判判別別法法 1,|.1.7,npnp nn 設(shè)設(shè) 是是一一個個正正整整數(shù)數(shù) 如如果果 定定理理對對所所有有的的素素數(shù)數(shù)都都有有則則 是是素素數(shù)數(shù). .1. 1.1.72. 1 對于比較小的整數(shù)，利用定理可以迅速判斷出它是否為素數(shù)。 每個不等于

10、的整數(shù)都有一個注：素因數(shù)。1.1.61.1.6,1( | )nppnpnn . .證證：反反證證法法（素素數(shù)數(shù)滿滿足足條條件件，排排除除合合數(shù)數(shù)可可能能）. .假假設(shè)設(shè)為為合合數(shù)數(shù)，題題設(shè)設(shè)和和定定理理相相矛矛盾盾. .因因為為根根據(jù)據(jù)定定理理它它的的大大于于 的的最最小小正正因因數(shù)數(shù)是是素素數(shù)數(shù)，且且因因此此，為為素素數(shù)數(shù)，且且滿滿足足假假設(shè)設(shè)條條件件. .16Eratosthenes2 2. .素素數(shù)數(shù)的的求求法法( (篩篩法法) )nn 1 1、要要求求出出不不超超過過 的的一一切切素素數(shù)數(shù), ,只只須須把把不不超超過過的的素素數(shù)數(shù)的的倍倍數(shù)數(shù)劃劃去去即即可可. . ,pppaap 2

11、22 2 2 2、要要劃劃掉掉素素數(shù)數(shù) 的的倍倍數(shù)數(shù), ,可可以以從從開開始始劃劃起起, ,因因?qū)τ谟诿棵恳灰粋€個小小于于的的合合數(shù)數(shù)它它的的最最小小素素因因數(shù)數(shù), , 因因而而在在之之前前已已被被劃劃掉掉了了. .17100N 求求出出所所有有不不超超過過例例2 2的的素素數(shù)數(shù). . 100102,3,5,7,2,3,5,71,1 100 解解 小小于于等等于于的的所所有有素素數(shù)數(shù)為為劃劃去去的的倍倍數(shù)數(shù)和和 余余下下的的即即為為之之間間的的素素數(shù)數(shù). .18146891011121314151617181920212223242526272829303132333435363738394

12、04142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979892357910019 1 1002, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 9725故故之之間間的的素素數(shù)數(shù)有有共共個個. .201.1.8 素素數(shù)數(shù)有有無無定定理理窮窮多多個個. .這這是是不不可可能能的的. .故故素素數(shù)數(shù)

13、有有無無窮窮多多個個. .kppp 證證( () ) 假假設(shè)設(shè)整整數(shù)數(shù)中中只只有有有有限限反反證證個個設(shè)設(shè)為為法法素素數(shù)數(shù), ,令令1 12 2， ， ， ，1knp pp ，1 12 2 inpikn 則則所所以以 是是合合數(shù)數(shù). .( ( = =1 1, ,2 2, , , ) ), ,n于于是是 的的大大于于 1(1)ip, ppik 的的最最小小正正因因數(shù)數(shù) 是是素素數(shù)數(shù) 這這里里某某個個 , , 12|kp| p ppp n因因此此（又又）, ,11.1.3p|（定定理理）21Comment-1：尚未找到產(chǎn)生素數(shù)的有效公式， 尋找大素數(shù)需要借助計算機Comment-2：假設(shè)某一個大數(shù)

14、是兩個素數(shù)的乘積（e.g.,1024 bits）,找到這兩個素數(shù)是一個困難問題，即大數(shù)分解問題。22三、歐幾里得除法三、歐幾里得除法(帶余除法帶余除法) () ,1.1.9,0a bbqrra = b + ,rbq 設(shè)設(shè)是是兩兩個個整整數(shù)數(shù), ,其其中中0,0,則則存存在在歐歐幾幾里里得得 定定唯唯一一除除的的得得法法理理整整數(shù)數(shù), ,使使,qabrab不不完完全全商商其其中中 叫叫做做 被被 除除所所得得的的叫叫做做 被被 除除所所得得的的余余數(shù)數(shù). ., q r存存在在證證 ( (的的) )性性 考考慮慮數(shù)數(shù)列列,bbbbbb, ,- -3 3 , ,- -2 2 , ,- - , ,0

15、0, , , ,2 2 , ,3 3 ,a則則 必必在在上上述述數(shù)數(shù)列列的的某某兩兩項項之之間間q即即存存在在整整數(shù)數(shù) , ,23a = bq+ rrb, 0, 0(1)qbaqb0abqb使使得得 ,rabq令令則則有有11,.q = qrr 故故從從而而11,q rq rqr( (的的) ) 若若有有整整數(shù)數(shù) , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb 若若則則而而矛矛盾盾. . 111,0, 0abqrrbabqrrb 24 0,0,1.1.9,0|:bbabqrrb如如果果將將條條件件改改為為則則定定理理中中結(jié)結(jié)論論可可改

16、改為為 注注|0.b aabr 被被 除除所所得得的的余余數(shù)數(shù)推推論論 1.1.7, 由由定定理理和和歐歐幾幾里里得得除除法法 可可得得判判斷斷一一個個整整數(shù)數(shù)是是否否為為素素數(shù)數(shù)的的方方法法. .137.N 例例3 3 證證明明為為素素數(shù)數(shù) 137122,3,5,7,11, 證證 因因小小于于等等于于的的素素數(shù)數(shù)有有25 2,3,5,7,11137,1.1.7,137N 所所以以皆皆不不能能整整除除由由定定理理知知為為素素數(shù)數(shù). .,NNNNN 一一般般地地, ,對對于于整整數(shù)數(shù), ,先先求求出出不不超超過過的的所所有有素素數(shù)數(shù) 若若這這些些素素數(shù)數(shù)都都不不能能整整除除則則為為素素數(shù)數(shù) 否否

17、則則為為合合數(shù)數(shù). . 13768 2,13745 3,1372712245,13719 7,137121. 51 又又 26 ) (1.1.1,0a bbcq ra = bq+ r,crbc 設(shè)設(shè)是是兩兩個個整整數(shù)數(shù), ,其其中中0 0, ,則則對對任任意意整整數(shù)數(shù) , ,存存在在唯唯一一的的整整歐歐幾幾里里數(shù)數(shù), ,使使 定定理理除除法法得得得得歐歐幾幾里里得得除除法法的的推推廣廣形形式式, q r存存在在證證 ( (的的) )性性 考考慮慮數(shù)數(shù)列列,bcbcbc c bcbcbc , ,- -3 3, ,- -2 2, ,- -, , , , ,2 2, ,3 3 ,a則則 必必在在上上

18、述述數(shù)數(shù)列列的的某某兩兩項項之之間間q即即存存在在整整數(shù)數(shù) , ,(1)qbcaqbc cabqbc 使使得得27a = bq+ rcrbc , , ,rabq令令則則有有11,.q = qrr 故故從從而而11,q rq rqr( (的的) ) 若若有有整整數(shù)數(shù) , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb 若若則則而而矛矛盾盾. . 111,abqrcrbcabqrcrbc 281.1.101.1.3c對對定定理理中中 的的某某些些特特定定義義 殊殊取取值值: : ,0,cbbrr 4 4. .當(dāng)當(dāng)時時 有有這這時時 叫叫做做最

19、最大大負(fù)負(fù)余余數(shù)數(shù). . 1.0,0,crbr 當(dāng)當(dāng)時時 有有這這時時 叫叫做做最最小小非非負(fù)負(fù)余余數(shù)數(shù). . 1,1,crbr 2 2. .當(dāng)當(dāng)時時 有有這這時時 叫叫做做最最小小正正余余數(shù)數(shù). . 1,10,cbb+rr 3 3. .當(dāng)當(dāng)時時 有有- -這這時時最最大大非非 叫叫做做 正正余余數(shù)數(shù). . 5.2 ,.22bbbk ckkrk 當(dāng)當(dāng)時時 有有- - 2 ,1,.22bbbk ckkrk 當(dāng)當(dāng)時時 有有- -29 21,bkck 當(dāng)當(dāng)時時 有有11.222bbbbkrk - - -2 2112bbkrk - -1 1- -= =2 2即即,b于于是是無無論論 取取偶偶數(shù)數(shù)還還是

20、是奇奇數(shù)數(shù) 總總有有.22bbbbrr- - 或或 - -2222r絕絕對對值值最最這這時時 叫叫做做小小余余數(shù)數(shù). .301.2 1.2 整數(shù)的表示整數(shù)的表示 11101,01,1,2, ,0.1.2.1kkkkiikbnna baba baaabika 設(shè)設(shè) 是是大大于于 的的正正整整數(shù)數(shù) 則則任任意意正正整整數(shù)數(shù)都都可可唯唯一一地地表表成成其其中中 是是整整數(shù)數(shù)且且首首項項系系 理理數(shù)數(shù) 定定證證 （）由由歐歐幾幾存存在在性性里里得得除除法法 000,01nbqaab 0111,01qbqaab 31 122221111,01,01,01kkkkkkkkqbqaabqbqaabqbqaa

21、b nb注注意意到到 和和 都都為為正正整整數(shù)數(shù)，12100kkqqqqqn -1(1,2,),0().ikkqiqbkq 因因為為整整數(shù)數(shù) 當(dāng)當(dāng)時時，必必有有整整數(shù)數(shù)使使算算法法停停止止得得1.kkqa 于于是是上上述述等等式式中中最最后后一一個個等等式式為為32 ,從從最最后后一一個個等等式式開開始始 依依次次代代入入上上一一等等式式, ,即即得得 1110kkkkna baba ba :n（）如如果果 有有兩兩種種不不同同的的一一性性表表示示式式唯唯 11101110,01,1,01,1,kkkkikkkkina baba baabiknc bcbc bccbik (00)kkac 這這

22、里里可可以以取取或或331111100()()()()0kkkkkkacbacbac bac 上上兩兩式式相相減減, ,得得 ,0,jjiiacij jac 設(shè)設(shè)而而當(dāng)當(dāng)（時時就就是是原原式式）時時則則有有11()()()0jkjkkjjjjbacbacbac 110,()()()0kjkkjjjjbacbacbac 因因所所以以有有 111()()kjjjkkjjacacbacb 因因此此有有 34|()jjbac 于于是是 |jjacb 01,01jjabcb 但但 |,jjacb又又有有矛矛盾盾. .n故故 的的表表示示式式是是唯唯一一的的. . 11011101101()01,0,1,

23、2, ,0.(.2).1kkbkkkkikkkbbna aa ana baba baabik ana aa an 用用表表示示展展開開式式其其中中稱稱為為整整 數(shù)數(shù) 定定義義表表示示的的 進(jìn)進(jìn)制制35 1 每每個個正正整整數(shù)數(shù)都都可可以以表表成成不不同同的的2 2 推推論論的的冪冪的的和和. .0321264211602321102101221225052100102200202400402800802160例例1 表示整數(shù)表示整數(shù)642為二進(jìn)制為二進(jìn)制因為：因為： 2642(1010000010) 所所以以3611111111F1515011101117 77 711101110E14140

24、11001106 66 611011101D1313010101015 55 511001100C1212010001004 44 410111011B1111001100113 33 310101010A1010001000102 22 2100110019 99 9000100011 11 1100010008 88 8000000000 00 0二進(jìn)制二進(jìn)制十六進(jìn)制十六進(jìn)制十進(jìn)制十進(jìn)制二進(jìn)制二進(jìn)制十六進(jìn)制十六進(jìn)制十進(jìn)制十進(jìn)制二進(jìn)制二進(jìn)制, ,十進(jìn)制和十六進(jìn)制換算表十進(jìn)制和十六進(jìn)制換算表37 一般地一般地, ,將十進(jìn)制轉(zhuǎn)換為二進(jìn)制比轉(zhuǎn)換為十六將十進(jìn)制轉(zhuǎn)換為二進(jìn)制比轉(zhuǎn)換為十六進(jìn)制要容易些進(jìn)制

25、要容易些. .因此要將十進(jìn)制轉(zhuǎn)換為十六進(jìn)制因此要將十進(jìn)制轉(zhuǎn)換為十六進(jìn)制, ,可先將十進(jìn)制轉(zhuǎn)換為二進(jìn)制可先將十進(jìn)制轉(zhuǎn)換為二進(jìn)制, ,再將二進(jìn)制轉(zhuǎn)換為十再將二進(jìn)制轉(zhuǎn)換為十六進(jìn)制六進(jìn)制.(.(四位二進(jìn)制數(shù)對應(yīng)一個十六進(jìn)制數(shù)四位二進(jìn)制數(shù)對應(yīng)一個十六進(jìn)制數(shù)) )321610(ABC8)10 1611 1610 168 (43976) 例例2 2 2222 A(1010) ,B(1011) , C(1100) ,8(1 0,30 0) 例例因因162101(ABC8)(101100110)0010 所所以以 102161040010 (642)(10)00(282 例例381.3 1.3 最大公因數(shù)與廣義

26、歐幾里得除法最大公因數(shù)與廣義歐幾里得除法一、最大公因數(shù)一、最大公因數(shù) 1212,(1.3.12),|(1,2, ),.nkna aan nd aknda aa 設(shè)設(shè)是是個個整整數(shù)數(shù) 若若整整數(shù)數(shù)則則稱稱 是是 的的一一個個 因因數(shù)數(shù)定定義義公公 121212,(,).nnna aaa aaa aa 若若不不全全為為零零, ,則則整整數(shù)數(shù)的的所所有有公公因因數(shù)數(shù)中中最最大大的的一一個個公公因因數(shù)數(shù)叫叫做做記記作作最最大大公公因因數(shù)數(shù). . 1212,(,)1,nna aaa aa 互互素素特特別別 當(dāng)當(dāng)時時 稱稱或或互互質(zhì)質(zhì). .39 1212120,( ),;(2)|,|.nnnda aad

27、| a d | ad | ae a e | ae | ae d 是是的的最最大大公公因因數(shù)數(shù)1 1 若若則則最最大大公公因因數(shù)數(shù)可可描描述述為為: : (14,21)7, ( 15,21)3, (14, 15,211.1) 例例 2,( , )( , ).a bb aa b 設(shè)設(shè)是是兩兩個個例例整整數(shù)數(shù) 則則 ,| ,3( , ).a bb aa bb 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 如如果果則則例例40 ,|,papapa 設(shè)設(shè) 是是一一個個素素數(shù)數(shù), , 為為 整整數(shù)數(shù) 如如果果則則例例與與4 4互互素素. .:素素數(shù)數(shù)與與任任一一整整數(shù)數(shù)有有如如下下關(guān)關(guān)系系 ,| ,|,dpd ap ap

28、 a 若若則則因因，于于是是與與題題設(shè)設(shè)矛矛盾盾 ( , ),|,1.p addppdp 證證 設(shè)設(shè)則則有有因因 是是素素數(shù)數(shù) 所所以以或或 1,( , )1.dp a 故故必必 從從而而41 (1)|,1,|,1.iid aindain 證證設(shè)設(shè)則則有有1212,|,|,|nna aaaaa故故的的公公因因數(shù)數(shù)也也是是的的公公因因數(shù)數(shù). . ,|,1,|,1.iidaind ain 反反之之 設(shè)設(shè)同同樣樣有有1212|,|,|,nnaaaa aa故故的的公公因因數(shù)數(shù)也也是是的的公公因因數(shù)數(shù). . (2)(1)(2).由由即即得得 1212121212,( ),|,|,|1.3.1|;(2)

29、(,)(|,|,|).nnnnna aana aaaaaa aaaaa 設(shè)設(shè)是是 個個不不全全為為零零的的整整數(shù)數(shù) 則則1 1與與的的公公 因因數(shù)數(shù)相相同同 定定理理42 ,( , )(, )( ,)(|,5|).a ba ba babab 設(shè)設(shè)是是兩兩個個整整數(shù)數(shù) 則則例例有有 1.3.2,().bb = b設(shè)設(shè) 是是任任一一正正整整數(shù)數(shù) 則則 0 0, ,定定理理 (0,21)21, ( 156,0)15, (0, ) |.bb 例例 0,(0, ).bbbb 證證 因因任任何何非非零零整整數(shù)數(shù)都都是是 的的因因數(shù)數(shù) 而而正正整整數(shù)數(shù)的的最最大大因因數(shù)數(shù)為為故故 43.dd ,.db cd

30、d 所所以以 是是的的公公因因數(shù)數(shù) 從從而而 ,.da bdd 同同理理可可證證, ,是是的的公公因因數(shù)數(shù) 因因而而故故 18591 1573286, 1573528614 ,73 例例因因(1859,1573)(1573,286)(286,143)143 所所以以 1., ,( , )( ,.).3 3a b ca = bq+cqa b = b c設(shè)設(shè)是是三三個個不不全全為為零零的的整整數(shù)數(shù) 如如果果其其中中 是是整整數(shù)數(shù) 定定理理則則 ( , ), ( , ),a bdb cdd | a d | b 證證 設(shè)設(shè)則則于于是是|()| ,d aq bd c 44二、廣義歐幾里得除法二、廣義歐幾

31、里得除法 111,0nnnnnrr qrr 01,.a bra rb設(shè)設(shè)是是任任意意兩兩個個正正整整數(shù)數(shù) 記記反反復(fù)復(fù)運運用用歐歐幾幾里里得得除除法法: : 011221,0,rr qrrr 122332,0,rr qrrr 2111,0,nnnnnnrrqrrr 12110,0.nnnrrrrbnr 因因為為所所以以經(jīng)經(jīng)過過有有限限步步驟驟, ,必必存存在在算算法法使使得得（）停停止止45 011223111.3.3,( , )( ,)( ,)( ,)(,)(,)(,0)nnnnnna br rr rr rrrr rrr 于于是是由由定定理理可可知知 1.3.4,( , ).nna bra

32、br 設(shè)設(shè)是是任任意意兩兩個個正正整整數(shù)數(shù)是是廣廣義義歐歐幾幾里里得得除除法法中中最最后后一一個個非非零零余余數(shù)數(shù) 則則 定定理理. 上上述述求求兩兩個個整整數(shù)數(shù)的的最最大大公公因因數(shù)數(shù)的的方方法法叫叫做做也也叫叫廣廣義義歐歐幾幾里里得得除除法法, ,輾輾轉(zhuǎn)轉(zhuǎn)相相除除法法做做46 1859,81573,( , ).aba b 計計算算例例設(shè)設(shè) 18591 1573286157352862862 143143解解 因因( 1859,1573)(1859,1573)143. 所所以以 46480,39423,( , ).aba b 計計算算例例設(shè)設(shè)9 9解解 最最小小非非負(fù)負(fù)余余數(shù)數(shù)法法46480

33、139423705739423570574138 47 522122 1 70571413829194138129191219 29192 121948112192481257 4811257224257122433 22463326331267 263757152 (46480, 39423)1. 所所以以 481nnnrr q 0112,rr qr 1223,rr qr 211,nnnnrrqr 在在廣廣義義歐歐幾幾里里得得除除法法中中, ,由由3221,nnnnrrqr 211,nnnnrrqr 1322,nnnnrrrq3122,rrr q 0211qrrr( , )satba b 1

34、232, ,nnrrr rs t逐逐次次消消去去可可找找到到整整數(shù)數(shù)使使得得49 1859,1573, ,( , )1.0abs tsatba b 設(shè)設(shè)求求整整數(shù)數(shù)使使得得 例例 18591 1573286157352862862 143143解解 因因( , )143.s =t =sa + tb = a b 所所以以有有整整數(shù)數(shù)5 5, ,6 6, ,使使得得 1573528615735(18591 1573143) 于于是是 1573528628618591431 1573 5( 1859)6 1573 50 1.,( , )0,1,2.5,3nnnna bs at ba bnst 設(shè)設(shè)是

35、是任任意意兩兩個個正正整整數(shù)數(shù), ,則則對對 定定于于這這里里歸歸為為理理納納地地定定義義 1211121100,0,1,10jjjjjjjjsssqsttstttq 2,3,jn jq其其中中是是廣廣義義歐歐幾幾里里得得除除法法中中的的不不完完全全商商. . :0,1,2,jjjjjns at brr 只只需需證證明明 對對于于其其中中 是是廣廣義義歐歐幾幾里里得得除除 法法中中分分析析: :的的余余數(shù)數(shù). . ( , )nnns at bra b ,jn 當(dāng)當(dāng)時時 就就有有51 0000001,0,0j =sts at barj 時時, ,由由題題設(shè)設(shè)以以及及知知結(jié)結(jié)論論對對于于成成立立.

36、 . j對對 作作數(shù)數(shù)學(xué)學(xué)歸歸納納法法. . 1111110,1,1j =sts at bbrj 時時, ,由由題題設(shè)設(shè)以以及及知知結(jié)結(jié)論論對對于于成成立立. . 11,jjjjks at br假假設(shè)設(shè)結(jié)結(jié)論論對對于于成成立立 即即52 211,kkkkjkrrrq 對對于于有有,由由歸歸納納假假設(shè)設(shè) 可可得得211211()()kkkkkksqsatqtb 21122111()()kkkkkkkkkrrrqsatbsatb q kks at bjk 結(jié)結(jié)論論對對于于也也成成立立. . j由由數(shù)數(shù)學(xué)學(xué)歸歸納納法法原原理理, ,結(jié)結(jié)論論對對于于所所有有的的 成成立立. .53 1.3,( , )

37、.5s tsatba b （）由由定定理理及及其其證證明明 可可得得求求算算整整數(shù)數(shù)得得法法使使的的方方法法. . 010101,1,00,1rarbsstt ,首首先先 令令 100(1)0,rsstt 如如果果則則令令.計計算算結(jié)結(jié)束束54 01201 11,rqrrq rr（）取取整整否否則則, ,計計算算 211(2)0,rsstt 如如果果則則令令.計計算算結(jié)結(jié)束束否否則則, ,計計算算 12312 22,rqrrq rr 201 1201 1,ssq sttq t 以以及及 55 11(3)0(3),jjjrjsstt 如如果果則則令令否否則則, ,計計算算 111,jjjjjjj

38、rqrrq rr 211211,jjjjjjjjssqsttqt 以以及及 10,nr 最最后后, ,一一定定有有這這時時, ,令令 ,nnsstt.計計算算結(jié)結(jié)束束56j a b 11023njq1q2q3qnqjr1jr 1r2r2r3r3r4rnr1nr 1js js2s2s1s3s1ns ns1jt jt1t2t2t3t1nt nt2q 2q :上上述述過過程程可可以以列列表表如如下下|t|s|(,)a b|00r 1r 01s 00t 10s 11t 57 112112111jjjjjjjjjjjjjjjrqrrq rssqstqtrt 1,2,jn 2,3,jn 010101,1,

39、00,1rarbsstt ,其其中中58j123456 737,635, )11(abs tsatba b 設(shè)設(shè)計計算算整整數(shù)數(shù)使使得得例例jqjr1jr 1js js1jt jt63573763510635110210011026230111 2311 410106 6 77233252529 29 31156 56 656530193224 |t|s|( , )a b59s193 737( 224) 6351,t 注注所所以以 ，：不不唯唯一一。 1.( ,3.,6)1,1a bs tsatb 存存在在整整數(shù)數(shù)使使然然理理得得而而，定定 ,|1,( , )1.d | sa + tbda b

40、 = d 所所以以 于于是是因因此此 1.3.5.證證 由由定定理理要要性性即即得得必必 ( , ),| ,| ,d = a bd a d b充充分分性性 設(shè)設(shè)則則因因sa + tb =1 11.3., , ,5( , )s t dsatbdds t 即即存存在在但但注注：定定理理的的逆逆命命題題不不成成立立，不不一一定定是是的的最最大大公公約約數(shù)數(shù)。60 ,():(1)| ,| ;(2)| ,| ,.| .1 3.7abdd = a,bd a d be a e be d 設(shè)設(shè) ， 是是任任意意兩兩個個不不全全為為零零的的整整數(shù)數(shù)是是正正整整數(shù)數(shù) 則則的的是是 定定理理若若則則充充要要條條件件

41、 ( , ),| ,| .da bd a d b 證證 若若則則顯顯然然 1.3.5, ,s tsa+ tb = d由由定定理理存存在在整整數(shù)數(shù)使使得得 | , | ,|,|.e a e be satbe d 于于是是若若則則因因而而 ,(1),da b反反之之 若若成成立立 則則 是是的的公公因因數(shù)數(shù); ;61 (2),| ,|,a be ded 則則若若成成立立的的公公因因數(shù)數(shù)于于是是任任一一 ,da b因因此此是是的的最最大大公公因因數(shù)數(shù). .1.3.7(1)(:2)定定理理中中條條件件和和可可以以作作為為最最大大公公因因注注數(shù)數(shù)的的定定義義. . , (1)(,)( , ).( , )

42、(2)| ,| ,(,).|(,)1.( , ).3 8)1( ,.abmam bma b ma ba bdd a d bd ddaba ba b 設(shè)設(shè) ， 是是任任意意兩兩個個不不全全為為零零的的整整數(shù)數(shù). .若若 是是任任一一正正整整數(shù)數(shù) 則則 若若非非零零整整數(shù)數(shù) 滿滿足足則則 特特別別地地, , 定定理理62|.ddm于于是是 ( , ),(,),da bdam bm 證證 ( (1 1) )設(shè)設(shè)則則存存在在整整satbd ,()()ms amt bmdm 兩兩端端同同乘乘以以得得 | ,| ,|,|,d a d bdm am dm bm又又因因|,dm d .mddmd = d而而和

43、和都都是是正正整整數(shù)數(shù), ,所所以以即即( , )(,).a b mma mb , ,s t數(shù)數(shù)使使得得63 (,)|ab=ddd (2)| ,|,(1)d a d b當(dāng)當(dāng)時時 由由有有 ( , )(|,|)(,)|ababa b =ddddddd ( , ), (,).|aba bddd 因因此此 ,( , ),da b 特特別別地地 取取時時 有有 (,)1.( , )( , )aba ba b 64 11200306,23200306,( , )12.aba b計計算算 例例設(shè)設(shè)(11,23) 200306200306 (11,23)1, 解解 因因所所以以( , )(11200306,

44、23200306)a b 12,:nna aa個個整整數(shù)數(shù)的的最最大大公公因因數(shù)數(shù)的的求求法法 121122233112,0,(,), (,),(,)(,1.3.,9).nnnnnna aanaa addaddada aad 設(shè)設(shè)是是 個個整整數(shù)數(shù), ,且且令令則則 定定理理65 (120 150 210 35). 計計算算最最大大公公因因數(shù)數(shù)，例例1 13 3 (120,150)(4, 5) 3030解解 因因(30,210)30 (30,35)5 (120 150 210 35)5. 所所以以, ,最最大大公公因因數(shù)數(shù) ，最最后后介介紹紹幾幾個個與與最最大大公公因因數(shù)數(shù)有有關(guān)關(guān)的的結(jié)結(jié)論論

45、：66 ,2121211.abra babr 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 若若 被被 除除的的最最小小正正余余數(shù)數(shù)是是 , ,則則被被除除的的最最小小 引引理理正正余余數(shù)數(shù)是是1(21)(21)brq , ,a bq r證證 對對用用歐歐幾幾里里得得除除法法, ,存存在在整整數(shù)數(shù)使使得得 ,1abqrrb 2121abq r 于于是是 2 21bqr2 (21)(21)rbqr (1)12 (,21)rb qq 其其中中為為整整數(shù)數(shù)知知結(jié)結(jié)論論成成立立. .67( , ),111.aba ba b 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù), ,則則2 2和和2 2的的最最 引引理理2 2大大 公公因因數(shù)

46、數(shù)是是2 2, a b證證 對對用用廣廣義義歐歐幾幾里里得得除除法法, ,得得 1111222123332111,0,0,0,0( , )nnnnnnnnnabqrrbbr qrrbrr qrrbrrqrbrrrarbq 68 11231221112321(21)(21)21(21)(21)21(21)(21)21(21)()21(21)21nnnnnrabrrbrrrrrnrrnrppppp 由由引引理理1 1 1121,nppp 其其中中是是整整數(shù)數(shù). . (21, 21)21nrab 由由廣廣義義歐歐幾幾里里得得除除法法知知, ,69 ,(21.3.101 21)1( , )aba ba

47、 b 定定理理設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 則則 ,=1. ,=1.2證證 由由引引理理 即即得得結(jié)結(jié)論論. . ,211.3|.1121baa bb a 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 則則 定定理理. . , 0abqrrb 證證 設(shè)設(shè) 121(21)(21), 02121abrrbq 由由引引理理1 1的的證證明明可可得得701212 (2 )(2 )1).rbqbqq 其其中中為為整整數(shù)數(shù) |b a. . 21|21210bar 于于是是 0r 711.4 1.4 整除的進(jìn)一步性質(zhì)及最小公倍數(shù)整除的進(jìn)一步性質(zhì)及最小公倍數(shù)一、整除的性質(zhì)一、整除的性質(zhì) , ,0,0.( , )(, )( ,

48、 )1.4.1a b cbca cab cb c 設(shè)設(shè)是是三三個個整整數(shù)數(shù), ,且且如如果果1,1,則則 定定理理 ,( , )1.31, ,.16a cs tsatc 反反之之 因因于于是是存存在在定定理理整整數(shù)數(shù)使使得得（） (, ),( , ).| ,| .dab cdb cdb dc 證證 令令則則有有 |,| .|.dab dcdd于于是是有有從從而而72 ,()()bs abtb cb 兩兩端端同同乘乘以以得得 |,| ,| ()() ,| .d ab d cd s abtb cd b 由由可可得得即即有有|.d d于于是是.dd 故故 , ,0,|,( , )1,| .a b c

49、cc aba cc b 設(shè)設(shè)是是三三個個整整數(shù)數(shù) 且且如如果果 則則 推推論論1.4.1|(, )( , ),cab cb c 證證 由由題題設(shè)設(shè)條條件件及及定定理理, ,有有| .c b從從而而73 ,|,| .1.4.2pp abp ap b設(shè)設(shè) 是是素素數(shù)數(shù) 若若則則或或定定理理 |,1.4.1| .p abp b又又因因由由定定理理之之推推論論有有 |,( , )1.pp ap a 證證 因因 是是素素數(shù)數(shù), ,所所以以若若則則 , ,( , )1,( , )1,1(, )1.4.3a b ca cb cab c 設(shè)設(shè) 定定是是整整數(shù)數(shù) 若若理理則則1.4.1,(, )( , )1.a

50、b cb c證證 由由題題設(shè)設(shè)及及定定理理有有1212,(, )1,1,(, )1.nina aa ca cina aa c 推推廣廣: :設(shè)設(shè)是是整整數(shù)數(shù) 如如果果則則74 1212,|,|.nnka aapp a aapa 設(shè)設(shè)是是整整數(shù)數(shù)是是素素 推推論論數(shù)數(shù). .如如果果則則某某個個 |,(, )1,1iippaapin 證證( (反反證證法法) ) 因因 是是素素數(shù)數(shù), ,所所以以若若則則12(, )1.na aap 于于是是有有 12|.np a aa與與題題設(shè)設(shè) 矛矛盾盾75二、最小公倍數(shù)二、最小公倍數(shù) 1212121212,|,|,|,.1.4.1nnnnna aanam am

51、amma aaa aaa aa設(shè)設(shè)是是 個個整整數(shù)數(shù) 若若則則 叫叫做做的的一一個個. . 的的所所有有公公倍倍數(shù)數(shù)中中最最小小正正整整數(shù)數(shù)叫叫做做記記作作 公公倍倍數(shù)數(shù)最最 公公數(shù)數(shù) 定定小小倍倍義義 12,(1)|, 1;(2)|, 1,|.niima aaaminaminm m 若若則則:易易知知76 ,(1)|, |,1|;(2) , .4.4a ba m b mab ma bab 設(shè)設(shè)是是兩兩個個互互素素的的正正整整數(shù)數(shù) 則則定定理理若若則則.mabt 于于是是|,a mmak 證證 ( (1 1) ) 因因, ,則則|,|,b mb ak又又即即( , )1,| ,a bb k 而

52、而所所以以,kbt 由由此此可可得得|.ab m故故 (2),|,|aba ba mb m顯顯然然是是的的公公倍倍數(shù)數(shù). .又又若若, , (1)|.ab m由由,aba b所所以以是是的的最最小小公公倍倍數(shù)數(shù) 故故 , .a bab 77123123, aaa aaa 于于是是 121212(,)1,1.4.4,.a aa aa a 證證 因因 由由定定理理 12,na aan設(shè)設(shè)是是 個個兩兩兩兩互互素素的的正正整整 推推數(shù)數(shù) 廣廣即即 1212(,)1,1,.ijnna ai jnija aaa aa , ,則則 1323123(,)(,)1,1.3.3 (,)1,a aa aa a a

53、 又又由由定定理理, ,123123,.a a aa a a ,如如此此繼繼續(xù)續(xù) 可可得得 1212,.nna aaa aa 78 ,(1) , . , ( , )1.( , )(2)|, |, , |.4.5.a baba ba b a baba ba m b ma bm設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù)即即若若定定則則則則理理, ,a b對對于于一一般般的的正正整整數(shù)數(shù)有有 12.( , )( , )abkka ba b ,ma b證證 ( (1 1) )設(shè)設(shè)是是的的一一個個公公倍倍數(shù)數(shù), ,那那么么存存在在整整1212,k kmak mbk 數(shù)數(shù)使使得得因因此此12,akbk 79(,)1.(

54、 , ) ( , )aba ba b 由由于于 1|,( , )bka b所所以以有有1,.( , )bkt ta b 即即有有為為某某個個整整數(shù)數(shù)1,( , )abmakta b于于是是,( , )abtta ba b另另一一方方面面, ,對對任任意意的的整整數(shù)數(shù) , ,顯顯然然是是的的公公,( , )aba bmmta b 所所以以的的任任一一公公倍倍數(shù)數(shù)可可表表成成的的形形式式. .倍倍數(shù)數(shù). .801,t 當(dāng)當(dāng)時時 得得到到最最小小公公倍倍數(shù)數(shù) , ( , )aba ba b 任任意意兩兩個個正正整整數(shù)數(shù)的的乘乘積積等等于于這這兩兩個個數(shù)數(shù)的的最最小小公公倍倍數(shù)數(shù)與與最最大大公公因因數(shù)

55、數(shù)的的乘乘積積. .這這兩兩個個數(shù)數(shù)的的最最小小公公倍倍數(shù)數(shù)不不但但是是最最小小的的正正倍倍數(shù)數(shù), ,且且是是另另外外的的公公倍倍此此定定理理表表明明: :數(shù)數(shù)的的因因數(shù)數(shù). . , , ()( , )abmta b tta b 為為整整數(shù)數(shù) (2)(1), a bm由由的的證證明明可可知知, ,的的任任一一公公倍倍數(shù)數(shù)可可表表成成 , |.a bm所所以以81, , , .m a bma mbm a b 推推論論 設(shè)設(shè)是是正正整整數(shù)數(shù) 則則 , .m a b 2,(,)m abma mbma mb 證證 2( , )m abm a b ( , )abma b 12122233112,1.4,

56、.,6nnnnnna aana ammammama aam 設(shè)設(shè)是是 個個整整數(shù)數(shù) 令令 定定理理, ,則則 = =. . , , .1p qp qpq 設(shè)設(shè)是是兩兩個個不不同同的的素素數(shù)數(shù) 則則例例82 120,150,210,35.2 計計算算最最小小公公倍倍數(shù)數(shù)例例4 5120,1504,5 3030600(4,5) 解解 因因20 7600,21020,7 30304200(20,7) 4200,35120,1 35120 354200120,150,210,354200. 故故 83 1212,1.1,.7,|.nnma aaa aam若若是是整整數(shù)數(shù)的的公公倍倍數(shù)數(shù) 則則 定定理理

57、n由由數(shù)數(shù)學(xué)學(xué)歸歸納納法法原原理理, ,命命題題對對所所有有的的 成成立立. .n證證 對對 作作數(shù)數(shù)學(xué)學(xué)歸歸納納法法. .21.4.5n 時時, ,由由定定理理, ,命命題題成成立立. .1(3nn假假設(shè)設(shè)) )時時, ,命命題題成成立立. .即即1121,|nnma aam 1|,nnmm 對對于于 , ,由由歸歸納納假假設(shè)設(shè), ,有有|,1.4.5,nam又又由由定定理理1,|.nnmam 11212,|.nnnnmaa aaa aam 而而, ,故故841.5 1.5 素數(shù)素數(shù) 算術(shù)基本定理算術(shù)基本定理 121212121.5.1(1),(), 1ssittjiin nnp ppppp

58、pnq qqqqqqst pqis 任任一一整整數(shù)數(shù)都都可可以以表表成成素素數(shù)數(shù)的的乘乘積積. .且且在在不不考考慮慮乘乘積積次次序序的的情情況況下下, ,表表達(dá)達(dá)式式是是的的. .算算術(shù)術(shù)基基本本唯唯即即其其中中 是是素素數(shù)數(shù) 且且若若其其中中 是是素素定定理理 一一 定定理理數(shù)數(shù). . 則則 1212,(1)ssnp ppppp 證證 用用數(shù)數(shù)學(xué)學(xué)歸歸納納法法證證明明表表達(dá)達(dá)式式 85n假假設(shè)設(shè)對對于于小小于于 的的正正整整數(shù)數(shù), ,結(jié)結(jié)論論成成立立. .n對對于于正正整整數(shù)數(shù) 2,n 時時 結(jié)結(jié)論論顯顯然然成成立立. .,(1).n若若 是是素素數(shù)數(shù) 則則式式顯顯然然成成立立 ,1,1n

59、b cnbcbncn 若若 是是合合數(shù)數(shù), ,則則存存在在正正整整數(shù)數(shù), ,使使得得 1212,uusbpppcppp 由由歸歸納納假假設(shè)設(shè) 有有 1212uusnbcpppppp 于于是是 86,1,(1).n 由由歸歸納納法法原原理理 對對于于所所有有的的整整數(shù)數(shù)式式成成立立,(1).ip適適當(dāng)當(dāng)改改變變的的次次序序 即即得得式式.再再證證表表達(dá)達(dá)式式的的一一性性唯唯 11,.jjp qpq 但但都都是是素素數(shù)數(shù) 所所以以 1212,ttnq qqqqq假假設(shè)設(shè)還還有有 ,jq其其中中是是素素數(shù)數(shù) 則則 1212(2)stp ppq qq 112|,tpq qq因因此此11,|,jjpqp

60、q因因 是是素素數(shù)數(shù) 故故存存在在使使得得871,kkpqp 同同理理, ,存存在在使使得得11.pq 即即有有 于于是是111kjppqpq 1(2),p代代入入消消去去得得22stppqq , 1iistpqis 重重復(fù)復(fù)上上述述過過程程 最最后后可可得得88121212,0,1,2,5(12). .ssisijnnpppispppppijn 任任一一大大于于1 1的的整整數(shù)數(shù) 能能夠夠唯唯一一地地表表示示成成 ( (* *) )其其中中為為素素數(shù)數(shù), , 分分解解式式( (* *) )叫叫做做定定標(biāo)標(biāo)準(zhǔn)準(zhǔn)分分的的理理解解式式. . 1212,1,2,0kiknnpppik 有有時時為為了