1、2022-2-51信息安全數(shù)學(xué)基礎(chǔ)2022-2-5計算機科學(xué)與技術(shù)學(xué)院2網(wǎng)絡(luò)安全(應(yīng)用技術(shù))密碼學(xué)(理論基礎(chǔ))信息安全信息安全數(shù)學(xué)(數(shù)論、代數(shù)和橢圓曲線理論)身份識別技術(shù)、防火墻技術(shù)、入侵檢測技術(shù)等2022-2-5計算機科學(xué)與技術(shù)學(xué)院3課程內(nèi)容課程內(nèi)容數(shù)論代數(shù)(群、環(huán)、域)-新第8章(第8,9,10,11,12章)橢圓曲線-新第9章(第13章)同余式(第3章)二次同余式與平方剩余(第4章)原根與指標(第5章)素性檢測(第6+14章)連分數(shù)(第7章)不定方程與同余(第2章)整數(shù)的可除性(第1章)2022-2-5計算機科學(xué)與技術(shù)學(xué)院4信息安全數(shù)學(xué)基礎(chǔ)第1章：整數(shù)的可除性數(shù)的集合：，-3，-2，-1

2、，0，1，2，3， 在數(shù)學(xué)中有一門稱為“整數(shù)論”的分支早在公元前50年左右，在我國第一部數(shù)學(xué)專著九章算術(shù)九章算術(shù)(作者不詳)的第一章中就開始討論整數(shù)，介紹了輾轉(zhuǎn)相除法它與公元前三世紀歐幾里德所著幾何原本幾何原本中介紹的輾轉(zhuǎn)相除法是各自獨立地總結(jié)出來的五世紀時，在我國的孫子算經(jīng)孫子算經(jīng)中更有聞名于世的中國剩余定理(即孫子定理)，也對整數(shù)做了研究整數(shù)論是研究整數(shù)的學(xué)科整數(shù)什么叫整數(shù)？整數(shù)的一部分最簡單的數(shù)學(xué)模型就是自然數(shù)自然數(shù)的嚴格定義是在集合論的基礎(chǔ)上，由Peano(皮亞諾)給出了自然數(shù)公理如果有一些對象(可數(shù)集)，除了它們的數(shù)目之外其它性質(zhì)我們不予考慮的話，我們就可以用自然數(shù)來數(shù)它們無窮大總有

3、一些數(shù)目由于太大而沒有名稱。這種現(xiàn)象或許就是人們第一次碰到無窮大這在古代就已經(jīng)導(dǎo)致這種嚴肅的問題：有沒有大得不能數(shù)的數(shù)？阿基米德在一本題為數(shù)沙器(公元前200年)的書中回答了他列舉了一系列增長很快的數(shù)目，并且通過體積的估計而證明：這些數(shù)目當中有些數(shù)目比地球上甚至比太陽系中的沙粒的數(shù)目還大素數(shù)的數(shù)目是有限多還是無窮多？有了研究的對象集合，再建立對象集合上的運算。一些乘法的經(jīng)驗表明，有些數(shù)是一些比1大的其它數(shù)的乘積而有些數(shù)，就沒有這種性質(zhì)-質(zhì)數(shù)(素數(shù))在歐幾里德的原本中，已經(jīng)有一個簡單而巧妙的推理能夠得出結(jié)論：質(zhì)數(shù)無窮質(zhì)數(shù)無窮多多計算機只能處理有限數(shù)和有限個數(shù)，計算機的計算模型，硬件體系結(jié)構(gòu)的設(shè)計

4、與實現(xiàn)，代數(shù)編碼，軟件設(shè)計與實現(xiàn)，計算機通信及密碼學(xué)等，都廣泛使用了整數(shù)理論而數(shù)學(xué)數(shù)學(xué)可以處理無窮大數(shù)論特點任意兩個整數(shù)可以相加，相減，相乘，結(jié)果仍是整數(shù)但兩個整數(shù)不一定能在整數(shù)的范圍內(nèi)相除，這是整數(shù)系統(tǒng)的特點研究整數(shù)就針對這一特點加以分析實際上，研究整數(shù)的性質(zhì)基本上就是要研究整除性和因數(shù)分解等問題以及其它一些有關(guān)的問題數(shù)論內(nèi)容介紹數(shù)論中一些最基本的事實介紹整數(shù)的一些最基本的性質(zhì)有時似乎在敘述或證明一些盡人皆知非常明顯的事實。實則并非如此有些事情，我們習(xí)而不察，知其然而不知其所以然。有些事情，雖然知道，卻知道的不確切若未特別指明，凡出現(xiàn)的數(shù)都是指整數(shù)本章主要內(nèi)容：整除的概念歐幾里得算法(*)整

5、數(shù)的表示最大公因子與廣義歐幾里得算法(*)最小公倍數(shù)素數(shù)與算數(shù)基本定理(*)素數(shù)定理2022-2-5計算機科學(xué)與技術(shù)學(xué)院11121.1 1.1 整除的概念整除的概念 歐幾里得除法歐幾里得除法一、整除基本概念及性質(zhì)一、整除基本概念及性質(zhì) ,0,| .1a bbqabqbaabb a 設(shè)設(shè)是是任任意意兩兩個個整整數(shù)數(shù), ,其其中中如如果果存存在在一一個個整整數(shù)數(shù) 使使得得等等式式成成立立, ,則則稱稱或或者者 被被 整整除除, ,記記作作整整除除定定義義 如如果果 不不能能整整除除則則記記作作,|.baba 因因數(shù)數(shù)如如果果則則 叫叫做做 的的而而 叫叫做做 的的倍倍數(shù)數(shù)| ,.b abaab寫寫

6、成成或或/.aa bb此此時時 可可q13 當當 遍遍歷歷整整數(shù)數(shù) 的的所所有有因因數(shù)數(shù)時時也也遍遍歷歷整整數(shù)數(shù) 的的所所有有因因數(shù)數(shù)(2), /.baa ba (1),.:baba 當當整整數(shù)數(shù) 的的所所有有因因數(shù)數(shù)時時也也遍遍歷歷整整數(shù)數(shù)注注遍遍 的的所所有有因因數(shù)數(shù)歷歷 對對任任何何整整數(shù)數(shù)有有(5)0,| .aa a 對對任任何何整整數(shù)數(shù)有有(3)0,| 0.bb 對對任任何何整整數(shù)數(shù)有有1|1|(4),.bb 若若則則(6)| ,|(),()|().b ababa2022-2-5計算機科學(xué)與技術(shù)學(xué)院1415 設(shè)設(shè)是是三三個個整整數(shù)數(shù). .則則定定理理若若1,0,0| ,| ,| .a

7、 bcc b b ac a12, | .q qc a因因是是整整數(shù)數(shù) 所所以以12|c bb aqq證證 設(shè)設(shè)，則則存存在在整整數(shù)數(shù) ， ，使使得得12bcqabq，于于是是有有21212()()abqcq qc q q16 定定設(shè)設(shè)是是三三個個整整. .則則理理數(shù)數(shù)若若, ,0| , | ,|2.a b cc a c bc ab 1212()abcqcqc qq 12| , | ,c a c bq q證證 因因所所以以存存在在整整數(shù)數(shù)使使得得 12,acqbcq 12,.qqc | ab因因是是整整數(shù)數(shù) 所所以以17 , ,0| , |3,.a b cc a c bs tc satb 設(shè)設(shè)是

8、是三三個個整整數(shù)數(shù). .若若則則對對任任意意整整數(shù)數(shù) , ,有有 , , 定定理理 12121122,0|,(1,2, ),|.4ninnna 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ù) 所所以以18 , ,0,| , | ., ,1,1.a b cc a c bs ts

9、atbc 設(shè)設(shè)是是三三個個整整數(shù)數(shù)如如果果存存在在整整數(shù)數(shù)使使得得 則則 例例1.c 故故 | , | ,1,c a c bsatb證證 因因且且所所以以有有c | satb |1,c19 ,| ,|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 練習(xí)：1. 設(shè)a，b是兩個給定的非零整數(shù)，且有整數(shù)x，y使得ax+by=

10、1.證明：若a|n且b|n，則ab|n2. 設(shè) 是整系數(shù)多項式。若d|b-c，則d|2022-2-5計算機科學(xué)與技術(shù)學(xué)院201110( ).nnnnf xa xaxa xa( )( )f bf c解答：1.證明：由n=n(ax+by)=(na)x+(nb)y,及ab|na，ab|nb 得證。2.證明： 又 得證。 2022-2-5計算機科學(xué)與技術(shù)學(xué)院211111( )( )()().()nnnnnnf bf ca bcabca bc|jjd bc22二、素數(shù)二、素數(shù)( (質(zhì)數(shù)質(zhì)數(shù)) )及其判別法及其判別法 0112nnnnn設(shè)設(shè)整整數(shù)數(shù)， ，如如果果除除了了和和外外， 沒沒有有其其它它因因數(shù)數(shù)

11、, ,則則 叫叫做做( (或或素素數(shù)數(shù)質(zhì)質(zhì)數(shù)數(shù)不不可可約約或或),),否否則則 叫叫定定數(shù)數(shù) 義義做做合合數(shù)數(shù). . 0, 1,:,nnnp當當整整數(shù)數(shù)時時和和同同為為素素數(shù)數(shù)或或合合數(shù)數(shù). .因因此此通通常常素素數(shù)數(shù)總總是是指指正正整整數(shù)數(shù) 用用注注表表示示. . 1. 素素數(shù)數(shù)23 ,1,6.npnppn 設(shè)設(shè) 是是一一個個正正合合數(shù)數(shù)是是 的的一一個個大大于于的的最最小小正正因因數(shù)數(shù) 則則 是是素素數(shù)數(shù), , 理理且且 定定 p假假設(shè)設(shè)矛矛盾盾, ,所所以以 是是素素數(shù)數(shù). . , 1,pqqp證證 若若 是是合合數(shù)數(shù) 則則存存在在整整數(shù)數(shù)使使得得 | ,| ,p nq n又又于于是是p

12、n這這與與 是是 的的最最小小正正因因數(shù)數(shù)的的 2,.pnpn因因此此故故 ,1npn因因 是是合合數(shù)數(shù)是是 的的大大于于 的的最最小小正正因因數(shù)數(shù), ,所所以以,n1 1存存在在整整數(shù)數(shù)使使得得 111npnpnn|.q p24整整數(shù)數(shù)為為素素數(shù)數(shù)的的判判別別法法 ,|7,npnpnn 設(shè)設(shè) 是是一一個個正正整整數(shù)數(shù) 如如果果對對所所 定定有有的的素素數(shù)數(shù)都都有有則則理理是是素素數(shù)數(shù). .Eratosthenes2.2.素素數(shù)數(shù)的的判判別別法法1(1(篩篩法法) )nn 1 1、求求不不超超過過 的的一一切切素素數(shù)數(shù), ,只只須須把把不不超超過過的的素素數(shù)數(shù)的的倍倍數(shù)數(shù)劃劃去去即即可可. .

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

14、3536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979892357910027 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ù)有有共共個個. .28 素素數(shù)數(shù)有有定定理理8 8無無窮窮多多個個. .這這是是不不可可能能的的

15、. .故故素素數(shù)數(shù)有有無無窮窮多多個個. .kppp 證證() () 假假設(shè)設(shè)整整數(shù)數(shù)中中只只有有有有限限反反證證個個設(shè)設(shè)為為法法素素數(shù)數(shù), ,令令1212， ， ， ， ， ， ，1knp pp，1212 inpikn 則則所所以以 是是合合數(shù)數(shù). .( =1,2, ),( =1,2, ),n于于是是 的的大大于于 1(1)ip, ppik的的最最小小正正因因數(shù)數(shù) 是是素素數(shù)數(shù) 這這里里某某個個 , , 12kp | p pp因因此此, ,1p |29三、歐幾里得除法三、歐幾里得除法(帶余除法帶余除法) () ,9,0a bbq ra = bq+ r,rb 設(shè)設(shè)是是兩兩唯唯一一個個整整數(shù)數(shù),

16、 ,其其中中0,0,則則的的歐歐幾幾里里得得存存在在整整 定定理理數(shù)數(shù), ,使使得得除除法法,qabrab不不完完全全商商其其中中 叫叫做做 被被 除除所所得得的的叫叫做做 被被 除除所所得得的的余余數(shù)數(shù). ., q r存存在在證證 ( (的的) )性性 考考慮慮數(shù)數(shù)列列,bbbbbb,-3 ,-2 ,- ,0, ,2 ,3,-3 ,-2 ,- ,0, ,2 ,3 ,a則則 必必在在上上述述數(shù)數(shù)列列的的某某兩兩項項之之間間q即即存存在在整整數(shù)數(shù) , ,30a = bq+ rrb, 0, 0(1)qbaqb0abqb使使得得 ,rabq令令則則有有11,.q = qrr 故故從從而而11,q r

17、q rqr( (的的) ) 若若有有整整數(shù)數(shù) , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb若若則則而而矛矛盾盾. . 111,0, 0abqrrbabqrrb31 0,0,9,0|:|bbabqrrb如如果果將將條條件件改改為為則則定定理理 注注中中結(jié)結(jié)論論可可改改為為|0.b aabr被被 除除所所得得的的余余數(shù)數(shù)推推論論 7, 由由定定理理 和和歐歐幾幾里里得得除除法法 可可得得判判斷斷一一個個整整數(shù)數(shù)是是否否為為素素數(shù)數(shù)的的方方法法. .137.N 例例3 3 證證明明為為素素數(shù)數(shù) 137122,3,5,7,11, 證證 因因

18、小小于于等等于于的的素素數(shù)數(shù)有有32 2,3,5,7,11137,7,137N 所所以以皆皆不不能能整整除除由由定定理理 知知為為素素數(shù)數(shù). .,NNNNN 對對于于整整數(shù)數(shù), ,先先求求出出不不超超過過的的所所有有素素數(shù)數(shù) 若若這這些些素素 一一數(shù)數(shù)都都不不能能整整除除則則為為素素般般地地, ,數(shù)數(shù) 否否則則為為合合數(shù)數(shù). . 1376821,1374532,1372752,1371974,13712 115.又又 2022-2-5計算機科學(xué)與技術(shù)學(xué)院332022-2-5計算機科學(xué)與技術(shù)學(xué)院3435 () ,10a bbcq ra = bq+ r,crbc 設(shè)設(shè)是是兩兩個個整整數(shù)數(shù), ,其其

19、中中0,0,則則對對任任意意整整數(shù)數(shù) , ,存存在在唯唯一一的的整整數(shù)數(shù), ,使使得得 歐歐幾幾里里 定定理理得得除除法法 歐歐幾幾里里得得除除法法的的推推廣廣形形式式, q r存存在在證證 ( (的的) )性性 考考慮慮數(shù)數(shù)列列,bcbcbc c bcbcbc,-3,-2,-, ,2,3,-3,-2,-, ,2,3 ,a則則 必必在在上上述述數(shù)數(shù)列列的的某某兩兩項項之之間間q即即存存在在整整數(shù)數(shù) , ,(1)qbcaqbccabqbc使使得得36a = bq+ rcrbc, , ,rabq令令則則有有11,.q = qrr 故故從從而而11,q rq rqr( (的的) ) 若若有有整整數(shù)數(shù)

20、 , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb若若則則而而矛矛盾盾. . 111,abqrcrbcabqrcrbc37c對對定定理理1010中中 的的某某些些特特定定義義3 3 殊殊取取值值: : ,0,cbbrr 4.4.當當時時 有有這這時時 叫叫做做最最大大負負余余數(shù)數(shù). . 1.0,0,crbr當當時時 有有這這時時 叫叫做做最最小小非非負負余余數(shù)數(shù). . 1,1,crbr2.2.當當時時 有有這這時時 叫叫做做最最小小正正余余數(shù)數(shù). . 1,10,cbb+rr 3.3.當當時時 有有- -這這時時最最大大非非 叫叫做做 正

21、正余余數(shù)數(shù). . 5.2 ,.22bbbk ckkrk 當當時時 有有- - 2 ,1,.22bbbk ckkrk 當當時時 有有- -38 21,bkck 當當時時 有有11.222bbbbkrk -2 2112bbkrk -1-1-=-=2 2即即,b于于是是無無論論 取取偶偶數(shù)數(shù)還還是是奇奇數(shù)數(shù) 總總有有.22bbbbrr- - 或或 - -2222r絕絕對對值值最最這這時時 叫叫做做小小余余數(shù)數(shù). .2022-2-5計算機科學(xué)與技術(shù)學(xué)院392022-2-5計算機科學(xué)與技術(shù)學(xué)院404122221444433336332)133|11123 7|33334444nnnnn 1 1、若若nZ

22、,nZ,求求證證：1)33|1)33|）思考題思考題作業(yè)2112)2| (1)(31)3)9|(31)7125 2141nnn nnppp 2n2n1 1、若若nZ,nZ,求求證證：1)168|131)168|13、設(shè)設(shè)素素數(shù)數(shù)，是是素素數(shù)數(shù)，則則是是合合數(shù)數(shù)。421.2 1.2 整數(shù)的表示整數(shù)的表示 11101,01,1,21, ,0.kkkkiikbnna baba baaabika 設(shè)設(shè) 是是大大于于 的的正正整整數(shù)數(shù) 則則任任唯唯一一意意正正整整數(shù)數(shù)都都可可地地表表成成其其中中 是是整整數(shù)數(shù)且且首首 定定理理項項系系數(shù)數(shù)證證 由由歐歐幾幾里里得得除除法法 000,01nbqaab 01

23、11,01qbqaab43 122221111,01,01,01kkkkkkkkqbqaabqbqaabqbqaab 注注意意到到12100kkqqqqqn (1,2,),0.ikqikq因因為為整整數(shù)數(shù) 所所以以必必有有整整數(shù)數(shù)使使得得1.kkqa 于于是是上上述述等等式式中中最最后后一一個個等等式式為為44 ,從從最最后后一一個個等等式式開開始始 依依次次代代入入上上一一等等式式, ,即即得得 1110kkkkna baba ba :n如如果果 有有兩兩種種不不同同的的表表示示式式 11101110,01,1,01,1,kkkkikkkkina baba baabiknc bcbc bcc

24、bik (00)kkac這這里里可可以以取取或或451111100()()()()0kkkkkkacbacbac bac 上上兩兩式式相相減減, ,得得 ,jjiiacijac設(shè)設(shè)而而當當時時則則有有11()()()0jkjkkjjjjbacbacbac 110,()()()0kjkkjjjjbacbacbac 因因所所以以有有 111()()kjjjkkjjacacbacb 因因此此有有 46|()jjbac 于于是是 |jjacb 01,01jjabcb但但 |,jjacb又又有有矛矛盾盾. .n故故 的的表表示示式式是是唯唯一一的的. . 11011101101()01,0,1,2, ,

25、0.().kkbkkkkikkkbna aa ana baba baabik anba aa an 用用表表示示展展開開式式其其中中稱稱為為整整數(shù)數(shù) 的的 進進 定定制制表表示示義義47 1 每每個個正正整整數(shù)數(shù)都都可可以以表表成成不不同同的的2 2 推推論論的的冪冪的的和和. .0321264211602321102101221225052100102200202400402800802160例例1 表示整數(shù)表示整數(shù)642為二進制為二進制因為：因為： 2642(1010000010) 所所以以4811111111F1515011101117 77 711101110E141401100110

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

27、因此要將十進制轉(zhuǎn)換為十六進制因此要將十進制轉(zhuǎn)換為十六進制, ,可先將十進制轉(zhuǎn)換為二進制可先將十進制轉(zhuǎn)換為二進制, ,再將二進制轉(zhuǎn)換為十再將二進制轉(zhuǎn)換為十六進制六進制.(.(四位二進制數(shù)對應(yīng)一個十六進制數(shù)四位二進制數(shù)對應(yīng)一個十六進制數(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例例1.3 1.3 最大公因數(shù)與廣義歐幾里得除法最大公因

28、數(shù)與廣義歐幾里得除法一、最大公因數(shù)一、最大公因數(shù)50 1212,(2),|(1,2, ),.1nkna 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 互互素素特特別別 當當時時 稱稱或或互互質(zhì)質(zhì). .51 1212120,( ),;(2)|,|.nnnda aad | a d | ad |

29、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ù) 如如果果則則例例52 ,|,papapa 設(shè)設(shè) 是是一一個個素素數(shù)數(shù), , 為為 整整數(shù)數(shù) 如如果果則則例例與與4 4互互素素. .:素素數(shù)數(shù)與與任任一一整整數(shù)數(shù)有有如如下下關(guān)關(guān)系系 ,| .| ,|,dpd ap apa 若若則則因因于于是

30、是與與題題設(shè)設(shè)矛矛盾盾 ( , ),|,1.p addppdp 證證 設(shè)設(shè)則則有有因因 是是素素數(shù)數(shù) 所所以以或或 1,( , )1.dp a故故必必 從從而而 |,|,|( , ).dd ab d abda b若若 為為 練練習(xí)習(xí)奇奇數(shù)數(shù)，則則53 (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).由由即即得得 1212

31、121212,( ),|,|,|;(2) (,)(|,|,|).1nnnnna aana aaaaaa aaaaa 設(shè)設(shè)是是 個個不不全全為為零零的的整整數(shù)數(shù) 則則1 1與與的的公公因因數(shù)數(shù)相相 定定理理同同 54 ,( , )(, )( ,)(|,5|).a ba ba babab 設(shè)設(shè)是是兩兩個個整整數(shù)數(shù) 則則例例有有 .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ù)為為

32、故故 如何才能計算出兩個整數(shù)的最大公因數(shù)哪？(*)方法1：直接分解兩個整數(shù)但當整數(shù)很大時不可行不可行(后面我們會講到大整數(shù)分解是很困難的事情)方法2：廣義歐幾里得算法廣義歐幾里得算法/輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法2022-2-5計算機科學(xué)與技術(shù)學(xué)院5556.dd ,.db cdd 所所以以 是是的的公公因因數(shù)數(shù) 從從而而 ,.da bdd 同同理理可可證證, ,是是的的公公因因數(shù)數(shù) 因因而而故故 18591 1573286, 1573528614 ,73例例因因(1859,1573)(1573,286)(286,143)143所所以以 , ,( , )( , ).a b ca = bq+ cqa b

33、= b c設(shè)設(shè)是是三三個個不不全全為為零零的的整整數(shù)數(shù) 如如果果其其中中 是是整整數(shù)數(shù)則則 定定理理3 3 ( , ), ( , ),a bdb cdd | a d | b證證 設(shè)設(shè)則則于于是是|()| ,d aq bd c 57二、廣義歐幾里得除法二、廣義歐幾里得除法 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)過過有有限限步

34、步驟驟, ,必必存存在在使使得得58 011223113,( , )( ,)( ,)( ,)(,)(,)(,0)nnnnnna br rr rr rrrr rrr 于于是是由由定定理理 可可知知 ,( , ).4nna bra br 設(shè)設(shè)是是任任意意兩兩個個正正整整數(shù)數(shù)是是廣廣義義歐歐幾幾里里得得除除法法中中最最后后一一個個 定定理理非非零零余余數(shù)數(shù) 則則. 上上述述求求兩兩個個整整數(shù)數(shù)的的最最大大公公因因數(shù)數(shù)的的方方法法叫叫做做也也叫叫廣廣義義歐歐幾幾里里得得除除法法, ,輾輾轉(zhuǎn)轉(zhuǎn)相相除除法法做做求最大公因數(shù)的步驟(*)：2022-2-5計算機科學(xué)與技術(shù)學(xué)院5960 1859,81573,(

35、 , ).aba b 計計算算例例設(shè)設(shè) 18591 1573286157352862862 143143解解 因因( 1859,1573)(1859,1573)143.所所以以 46480,39423,( , ).aba b計計算算例例設(shè)設(shè)9 9解解 法法一一：最最小小非非負負余余數(shù)數(shù)4648013942370573942357057413861 522122 1 70571413829194138129191219 29192 121948112192481257 4811257224257122433 22463326331267 263757152 (46480, 39423)1. 所所

36、以以 6239423670572919 705722919121929192 1219481 12193481224481222433 224733733572 732122 1法法二二：絕絕對對值值最最小小余余數(shù)數(shù)464801394237057 (46480, 39423)1. 所所以以 631nnnrr q 0112,rr qr1223,rr qr211,nnnnrrqr在在廣廣義義歐歐幾幾里里得得除除法法中中, ,由由3221,nnnnrrqr211,nnnnrrqr 1322,nnnnrrrq3122,rrr q2011rrr q( , )satba b1232, ,nnrrr rs

37、t逐逐次次消消去去可可找找到到整整數(shù)數(shù)使使得得64 1859,1573, ,( , )1.0abs tsatba b 設(shè)設(shè)求求整整數(shù)數(shù)使使得得 例例 18591 1573286157352862862 143143解解 因因( , )143.s =t =sa + tb = a b 所所以以有有整整數(shù)數(shù)5,6,5,6,使使得得 1573528615735(18591 1573143) 于于是是 1573528628618591431 1573 5( 1859)6 1573 65 ,( , )0,1,2,5,nnnna bs at ba bnst 設(shè)設(shè)是是任任意意兩兩個個正正整整數(shù)數(shù), ,則則對對

38、于于這這里里歸歸 納納 定定理理地地定定義義為為 01211012111,0,0,0,jjjjjjjjssssqsttttqt 2,3,jn jq其其中中是是廣廣義義歐歐幾幾里里得得除除法法中中的的不不完完全全商商. . :0,1,2,jjjjjns at brr 只只需需證證明明 對對于于其其中中 是是廣廣義義歐歐幾幾里里得得除除 法法中中分分析析: :的的余余數(shù)數(shù). . ( , )nnns at bra b ,jn 當當時時 就就有有66 0000001,0,0j =sts at barj 時時, ,由由題題設(shè)設(shè)以以及及知知結(jié)結(jié)論論對對于于成成立立. . j對對 作作數(shù)數(shù)學(xué)學(xué)歸歸納納法法.

39、 . 1111110,1,1j =sts at bbrj 時時, ,由由題題設(shè)設(shè)以以及及知知結(jié)結(jié)論論對對于于成成立立. . 11,jjjjks at br假假設(shè)設(shè)結(jié)結(jié)論論對對于于成成立立 即即67 211,kkkkjkrrrq 對對于于有有,由由歸歸納納假假設(shè)設(shè) 可可得得211211()()kkkkkksqsatqtb 21122111()()kkkkkkkkkrrrqsatbsatb qkks at bjk 結(jié)結(jié)論論對對于于也也成成立立. . j由由數(shù)數(shù)學(xué)學(xué)歸歸納納法法原原理理, ,結(jié)結(jié)論論對對于于所所有有的的 成成立立. .68 5,( , )s tsatba b 由由定定理理 及及其其證

40、證明明 可可得得求求整整數(shù)數(shù)使使得得的的方方法法. . 010101,1,00,1rarbsstt ,首首先先 令令 100(1)0,rsstt 如如果果則則令令.計計算算結(jié)結(jié)束束69 01201 11,rqrrq rr否否則則, ,計計算算 211(2)0,rsstt 如如果果則則令令.計計算算結(jié)結(jié)束束否否則則, ,計計算算 12312 22,rqrrq rr 201 1201 1,ssq sttq t以以及及 70 11(3)0(3),jjjrjsstt如如果果則則令令否否則則, ,計計算算 111,jjjjjjjrqrrq rr 211211,jjjjjjjjssqsttqt以以及及 1

41、0,nr 最最后后, ,一一定定有有這這時時, ,令令 ,nnsstt.計計算算結(jié)結(jié)束束71ja(r0) b(r1)101100123njq1q2q3qnqjr1jr 1r2r2r3r3r4rnr1nr 1js js2s2s1s3s1ns ns1jt jt1t2t2t3t1nt nt2q 2q :上上述述過過程程可可以以列列表表如如下下|t|s|(,)a b|072 111211211jjjjjjjjjjjjjjjrqrrrq rssqsttqt 1,2,jn 2,3,jn 010101,1,00,1rarbsstt ,其其中中73j 0123456 737,635, )11(abs tsat

42、ba b設(shè)設(shè)計計算算整整數(shù)數(shù)使使得得例例jqjr1jr 1js js1jt jt63573763510635110210011026230111 2311 410106 6 77233252529 29 31156 56 656530193224 |t|s|( , )a b74193737( 224)6351 所所以以 5, , ,s t dsatbdda b定定理理 的的逆逆命命題題不不成成立立 即即若若有有整整數(shù)數(shù)使使 注注: : 但但 未未必必是是的的最最大大公公因因數(shù)數(shù). . ( , )1, ,61a bs tsatb存存在在整整數(shù)數(shù)使使得得定定理理 ,|1,( , )1.d | sa

43、 + tbda b = d 所所以以 于于是是因因此此 5.證證 由由性性定定理理要要即即得得必必 ( , ),| ,| ,d = a bd a d b充充分分性性 設(shè)設(shè)則則因因sa + tb =1 1是否也有是否也有(a，d)=1和和(b，c)=1？2022-2-5計算機科學(xué)與技術(shù)學(xué)院7576 ,():(1)| ,| ;(2)| ,| ,|.abdd = a,bd a d be a e be d 定定 設(shè)設(shè) ， 是是任任意意兩兩個個不不全全為為零零的的整整數(shù)數(shù)是是正正整整數(shù)數(shù) 則則的的是是若若則則要要理理充充條條件件7 7 ( , ),| ,| .da bd a d b 證證 若若則則顯顯然

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

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

46、數(shù)使使得得79 (,)|ab=ddd (2)| ,|,(1)d a d b當當時時 由由有有 ( , )(|,|)(,)|ababa b =ddddddd ( , ), (,).|aba bddd 因因此此 ,( , ),da b 特特別別地地 取取時時 有有 (,)1.( , )( , )aba ba b 80 11 200306,23 200306,( , )12.aba b計計算算 例例設(shè)設(shè)(11,23) 200306200306 (11,23)1, 解解 因因所所以以( , )(11200306,23200306)a b 12,:nna aa個個整整數(shù)數(shù)的的最最大大公公因因數(shù)數(shù)的的求求

47、法法 121122233112,0,(,), (,),(,)(,).nnnnnna aanaa addaddada aad 設(shè)設(shè)是是 個個整整數(shù)數(shù), ,且且令令則則 定定理理9 9 81 (120 150 210 35). 計計算算最最大大公公因因數(shù)數(shù)，例例1313 (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é)論論：歐幾里得除法的應(yīng)用：2022-2-5計算機科學(xué)與技術(shù)學(xué)院82 ,(21 21)1( , )10a

48、ba ba b 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 則則 , ,定定理理=1.=1. ,2121211.abra babr 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 若若 被被 除除的的最最小小正正余余數(shù)數(shù)是是 , ,則則被被除除的的最最小小 引引理理正正余余數(shù)數(shù)是是( , ),111.aba ba b 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù), ,則則2 2和和2 2的的最最 引引理理2 2大大 公公因因數(shù)數(shù)是是2 283 ,2121211.abra babr 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 若若 被被 除除的的最最小小正正余余數(shù)數(shù)是是 , ,則則被被除除的的最最小小 引引理理正正余余數(shù)數(shù)是是1(21)(21)brq, ,

49、a bq r證證 對對用用歐歐幾幾里里得得除除法法, ,存存在在整整數(shù)數(shù)使使得得 ,1abqrrb2121abq r 于于是是 2 21bqr2 (21)(21)rbqr(1)12 (21),rb qq 其其中中為為整整數(shù)數(shù)知知結(jié)結(jié)論論成成立立. .84( , ),111.aba ba b 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù), ,則則2 2和和2 2的的最最 引引理理2 2大大 公公因因數(shù)數(shù)是是2 2, a b證證 對對用用廣廣義義歐歐幾幾里里得得除除法法, ,得得 1111222123332111,0,0,0,0( , )nnnnnnnnnabqrrbbr qrrbrr qrrbrrqrbrrra

50、rbq 85 11231221112321(21)(21)21(21)(21)21(21)(21)21(21)()21(21)21nnnnnrabrrbrrrrrnrrnrppppp 由由引引理理1 1 1121,nppp 其其中中是是整整數(shù)數(shù). . (21, 21)21nrab 由由廣廣義義歐歐幾幾里里得得除除法法知知, ,86 ,(21 21)1( , )10aba ba b 設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 則則 , ,定定理理=1.=1.2證證 由由引引理理 即即得得結(jié)結(jié)論論. . 11,21| 21|baa bb a設(shè)設(shè)是是兩兩個個正正整整數(shù)數(shù) 則則 定定理理. . , 0abqrrb證

51、證 設(shè)設(shè) 121(21)(21), 02121abrrbq由由引引理理1 1的的證證明明可可得得871212 (2 )(2 )1).rbqbqq其其中中為為整整數(shù)數(shù) |b a. .r 221| 2110ba于于是是 0r 1.4 1.4 整除的進一步性質(zhì)及最小公倍數(shù)整除的進一步性質(zhì)及最小公倍數(shù)一、整除的性質(zhì)一、整除的性質(zhì)88 , ,0,0.( , )(, )( ,1)a b cbca cab cb c 設(shè)設(shè)是是三三個個整整數(shù)數(shù), ,且且如如果果1,1,則則 定定理理 ,( , )1, ,1a cs tsatc 反反之之 因因于于是是存存在在整整數(shù)數(shù)使使得得 (, ),( , ).| ,| .d

52、ab cdb cdb dc證證 令令則則有有 |,| .|.dab dcdd于于是是有有從從而而89 ,()()bs abtb cb兩兩端端同同乘乘以以得得 |,| ,| ()() ,| .d ab d cd s abtb cd b 由由可可得得即即有有|.d d于于是是.dd 故故 , ,0,|,( , )1,| .a b ccc aba cc b 設(shè)設(shè)是是三三個個整整數(shù)數(shù) 且且如如果果 則則 推推論論|(, )( , ),cab cb c 證證 由由題題設(shè)設(shè)條條件件及及定定理理1,1,有有| .c b從從而而90 ,|,2| .pp abp ap b定定設(shè)設(shè) 是是數(shù)數(shù) 若若則則或或理理素素

53、 |,1| .p abp b又又因因由由定定理理 之之推推論論有有 |,( , )1.pp ap a 證證 因因 是是素素數(shù)數(shù), ,所所以以若若則則2022-2-5計算機科學(xué)與技術(shù)學(xué)院91 , ,( , )1,( , )13,(, )1.a b ca cb cab c 設(shè)設(shè)是是整整數(shù)數(shù) 若若則則 定定理理1,(, )( , )1.ab cb c證證 由由題題設(shè)設(shè)及及定定理理 有有1212,(, )1,1,(, )1.nina aaca cina aac 推推廣廣: :設(shè)設(shè)是是整整數(shù)數(shù) 如如果果則則92 1212,|,|.nnka aapp a aapa 設(shè)設(shè)是是整整數(shù)數(shù)是是素素 推推論論數(shù)數(shù).

54、 .如如果果則則某某個個 |,(, )1,1iippaapin 證證( (反反證證法法) ) 因因 是是素素數(shù)數(shù), ,所所以以若若則則12(, )1.na aap 于于是是有有 12|.np a aa與與題題設(shè)設(shè) 矛矛盾盾練習(xí)：設(shè)k是正整數(shù)，證明： (1)(ak, bk)=(a, b)k (2)設(shè)a，b是正整數(shù)，若(a，b)=1，ab=ck，則a=(a, c)k，b=(b, c)k提示： (a, b)=1(ak-1, b)=1 a=a(ak-1, b)=(ak, ab)=(ak, ck)2022-2-5計算機科學(xué)與技術(shù)學(xué)院9394二、最小公倍數(shù)二、最小公倍數(shù) 1212121212,|,|,|,

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

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

57、由定定理理3,3,123123,.a aaa a a ,如如此此繼繼續(xù)續(xù) 可可得得 1212,.nna aaa aa 97 ,(1) , . , ( , ).( , )(2)|,|, , |.5a 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 98(,)1.( , ) ( , )ab

58、a 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ù). .991,t 當當時時 得得到到最最小小公公倍倍數(shù)數(shù) , ( , )aba ba b 任任意意兩兩個個正正整整數(shù)數(shù)的的乘乘積積等等于于這這兩兩個個數(shù)數(shù)的的最最小小公公倍倍數(shù)數(shù)與與最最大大公公因因數(shù)數(shù)的的乘乘積積. .這這

59、兩兩個個數(shù)數(shù)的的最最小小公公倍倍數(shù)數(shù)不不但但是是最最小小的的正正倍倍數(shù)數(shù), ,且且是是另另外外的的公公倍倍此此定定理理表表明明: :數(shù)數(shù)的的因因數(shù)數(shù). . , , ()( , )abmta b tta b為為整整數(shù)數(shù) (2)(1), a bm由由的的證證明明可可知知, ,的的任任一一公公倍倍數(shù)數(shù)可可表表成成 , |.a bm所所以以100, , , .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,6,nnnnnna aana a

60、mmammama aam 設(shè)設(shè)是是 個個整整數(shù)數(shù) 令令,則則 = =定定理理. . , , .1p qp qpq 設(shè)設(shè)是是兩兩個個不不同同的的素素數(shù)數(shù) 則則例例101 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. 故故 102 1212,|.nnma aaa aam若若是是整整數(shù)數(shù)的的公公倍倍數(shù)數(shù) 則則 定定理理7 7n由由數(shù)數(shù)學(xué)學(xué)歸歸納納法法原原理理, ,命命