第1章-整數(shù)的可除性課件

1、信息安全數(shù)學(xué)基礎(chǔ) 周杰課程簡介教學(xué)方式：理論課教學(xué)總學(xué)時：48考核方式：考試(70%)+(作業(yè)+平時) (30%)課程學(xué)分：3先修課程：無 教材、參考書：陳恭亮 信息安全數(shù)學(xué)基礎(chǔ) 簡明信息安全數(shù)學(xué)基礎(chǔ) 潘承洞,潘承彪 初等數(shù)論后續(xù)課程：密碼學(xué)與安全協(xié)議密碼學(xué)簡介 密碼學(xué) Cryptology維基百科：研究如何隱密地傳遞信息的學(xué)科 是指對信息以及其傳輸?shù)臄?shù)學(xué)性質(zhì)的研究，是數(shù)學(xué)和計算機(jī)科學(xué)的分支，和信息論密切相關(guān)。Wo ent out nh u ote ll orm dic e kodw? yemiiWould you like to come to dinner with me?密碼學(xué)簡介 密碼

2、學(xué) Cryptology百度百科：研究編制密碼和破譯密碼技術(shù)的科學(xué) 研究密碼變化的客觀規(guī)律，應(yīng)用于編制密碼以保守通信秘密的，稱為編碼學(xué)；應(yīng)用于破譯密碼以獲取通信情報的，稱為解碼學(xué)，總稱密碼學(xué)密碼學(xué)簡介 密碼學(xué) Cryptology 密碼學(xué)是信息安全中的相關(guān)議題，如認(rèn)證、訪問控制的核心。密碼學(xué)的首要目的是隱藏信息的涵義，并不是隱藏信息的存在。 密碼學(xué)已被應(yīng)用在日常生活：包括自動柜員機(jī)的芯片卡、電腦使用者存取密碼、電子商務(wù)等等。密碼學(xué)簡介 明文(plaintext)任何人都讀得懂的文字密文(encrypted; cipher text)用特殊方法使明文內(nèi)容變得混亂，使得只有持有“密鑰”的人才能恢復(fù)

3、出明文。Encrypt / decrypt加密 / 解密密碼學(xué)簡介 明文(plaintext) Would you like to come to dinner with me?密文(encrypted; cipher text)：加密 (Encrypt) Wo ent out nh u ote ll orm dic e kodw? yemii解密 (decrypt) Would you like to come to dinner with me?保密系統(tǒng)模型 保密系統(tǒng)模型圖 搭線信道 搭線信道 非法 (主動攻擊) (被動攻擊) 密碼分析員m 接入者 c (竊聽者) 信 源m 加密器 c 解

4、密器m 接收者mc=Ek1(m) 信道m(xù)=D k2(c) k1 k2 密鑰源 密鑰源 k1 密鑰信道 k2 m明文密文監(jiān)聽、截取、更改、增加加密密鑰解密密鑰加密方法解密方法明文機(jī)密性防止竊聽完整性內(nèi)容不可被更改鑒定性確定信息確實是由真正的發(fā)送者所傳送不可否認(rèn)性發(fā)送方在事后不可否認(rèn)其傳送的消息密碼學(xué)主要目標(biāo) 密碼學(xué)歷史 密碼學(xué)的歷史已有四千多年 早期的密碼學(xué)主要作為軍事用途。Caesar Cipher (凱撒密碼)(2千年前羅馬)每個字母用其前(后)面的字母替代A Z; B A; 一般形式，Caesar Cipher 中字母移動的位數(shù)可以為1-25中的任何一個DECHEXCHARACTER (C

5、ODE)DECHEXCHARACTER (CODE)00NULL1610DATA LINK ESCAPE (DLE)11START OF HEADING (SOH)1711DEVICE CONTROL 1 (DC1)22START OF TEXT (STX)1812DEVICE CONTROL 2 (DC2)33END OF TEXT (ETX)1913DEVICE CONTROL 3 (DC3)44END OF TRANSMISSION (EOT)2014DEVICE CONTROL 4 (DC4)55END OF QUERY (ENQ)2115NEGATIVE ACKNOWLEDGEMEN

6、T (NAK)66ACKNOWLEDGE (ACK)2216SYNCHRONIZE (SYN)77BEEP (BEL)2317END OF TRANSMISSION BLOCK (ETB)88BACKSPACE (BS)2418CANCEL (CAN)99HORIZONTAL TAB (HT)2519END OF MEDIUM (EM)10ALINE FEED (LF)261ASUBSTITUTE (SUB)11BVERTICAL TAB (VT)271BESCAPE (ESC)12CFF (FORM FEED)281CFILE SEPARATOR (FS) RIGHT ARROW13DCR

7、(CARRIAGE RETURN)291DGROUP SEPARATOR (GS) LEFT ARROW14ESO (SHIFT OUT)301ERECORD SEPARATOR (RS) UP ARROW15FSI (SHIFT IN)311FUNIT SEPARATOR (US) DOWN ARROWASCII Table Codes DECHEXCHARACTER DECHEXCHARACTERDECHEXCHARACTER320 x20640 x40960 x60330 x21!650 x41A970 x61a340 x22660 x42B980 x62b350 x23#670 x43

8、C990 x63c360 x24$680 x44D1000 x64d370 x25%690 x45E1010 x65e380 x26&700 x46F1020 x66f390 x27710 x47G1030 x67g400 x28(720 x48H1040 x68h410 x29)730 x49I1050 x69i420 x2A*740 x4AJ1060 x6Aj430 x2B+750 x4BK1070 x6Bk440 x2C,760 x4CL1080 x6Cl450 x2D-770 x4DM1090 x6Dm460 x2E.780 x4EN1100 x6En470 x2F/790 x4FO1

9、110 x6Fo480 x300800 x50P1120 x70p490 x311810 x51Q1130 x71q500 x322820 x52R1140 x72rDECHEXCHARACTER DECHEXCHARACTERDECHEXCHARACTER510 x333830 x53S1150 x73s520 x344840 x54T1160 x74t530 x355850 x55U1170 x75u540 x366860 x56V1180 x76v550 x377870 x57W1190 x77w560 x388880 x58X1200 x78x570 x399890 x59Y1210

10、x79y580 x3A:900 x5AZ1220 x7Az590 x3B;910 x5B1230 x7B600 x3C940 x5E1260 x7E630 x3F?950 x5F_1270 x7F其中從32 到 126 為可寫字符(Writable characters )，共95個。即10(數(shù)字)33(標(biāo)點符號)26*2(大小寫字母) 95個。 字母ABCDEFGASCII碼65666768697071大寫字母的ASCII 碼字母HIJKLMNASCII碼72737475767778字母OPQRSTUASCII碼79808182838485字母VWXYZASCII碼8687888990明文P

11、： WE WILL BEGINyx10加密方法密鑰為1097 79 97 83 86 86 76 79 81 83 88yy26 當(dāng) y 90yy 當(dāng) y 9071 79 71 83 86 86 76 79 81 83 88W E W I L L B E G I N87 69 87 73 76 76 66 69 71 73 78明文P：密文C：G O G S V V L O Q S X凱撒密碼的數(shù)學(xué)原理明文P： WE WILL BEGIN71 79 71 83 86 86 76 79 81 83 88xy10解密方法密鑰為1061 69 61 73 76 76 66 69 71 73 78xx

12、26 當(dāng) y 65xx 當(dāng) y 6587 69 87 73 76 76 66 69 71 73 78W E W I L L B E G I N明文P：密文C：G O G S V V L O Q S X阿拉伯人發(fā)明頻率攻擊方法(9世紀(jì))第一次世界大戰(zhàn)無線電的發(fā)明，電碼本。第二次世界大戰(zhàn)以機(jī)械代替人手的加密方法。密碼學(xué)歷史 德國的洛倫茲密碼機(jī)，加密機(jī)密郵件上世紀(jì)70年代中期, 首次出現(xiàn)了現(xiàn)代分組密碼DES1976年，Diffie和Hellman 在“密碼學(xué)新方向”一文中首次提出公鑰密碼的思想使用兩個密鑰：公鑰、私鑰加密和解密不是對稱的是對對稱密碼的重要補(bǔ)充DiffieHellman密鑰交換方法Di

13、ffie W, Hellman M E. New directions in cryptography J. IEEE Transactions on Information Theory, 1976,22(6): 644654 密碼學(xué)歷史 1978年，由MIT的 Rivest, Shamir & Adleman給出一種公鑰密碼算法RSA算法最著名的且被廣泛應(yīng)用的公鑰加密體制 利用數(shù)論的方法明文、密文是0到n-1之間的整數(shù)，通常n的大小為1024位二進(jìn)制數(shù)或309位十進(jìn)制數(shù)。Rivest, R. L., Shamir, A., Adleman, L. A.: A method for obta

14、ining digital signatures and public-key cryptosystems; Communications of the ACM, Vol.21, Nr.2, 1978, S.120-126. 密碼學(xué)歷史 2002年他們被授予圖靈獎（Turing Award）： “授予Ronald L. Rivest, Adi Shamir, Leonard M. Adleman圖靈獎以表彰其使得公鑰密碼技術(shù)在實際中應(yīng)用的創(chuàng)造性貢獻(xiàn)。” RSA算法是當(dāng)前在互聯(lián)網(wǎng)傳輸、銀行以及信用卡產(chǎn)業(yè)中被廣泛使用的安全基本機(jī)制。 Rivest, R. L., Shamir, A., Adlem

15、an, L. AShamir2008年4月24日下午 世界著名密碼學(xué)家、圖靈獎獲得者以色列Weizmann科學(xué)院教授 Adi Shamir教授做客清華論壇2010年5月山東大學(xué)授予Adi Shamir教授名譽(yù)博士學(xué)位 第一章 整數(shù)的可除性 1.1 整除的概念 歐幾里德除法 定義1 設(shè)a，b是任意兩個整數(shù)，b0。若有整數(shù)q使 abq，就稱b整除a，或a被b整除，記作b|a，并把b叫a的因數(shù)，a叫b的倍數(shù)。q也整除a，或a被q整除，即有q|a，并且q是a的因數(shù)，a也是q的倍數(shù)。記做整數(shù)：Z, -2, -1, 0, 1, 2, 定義1 如果使得abq的整數(shù)q不存在，稱b不整除a，或a不能被b整除。記

16、作b | a。整除的性質(zhì)：1. 如果b整除a， 即abq。則(1) 當(dāng)b遍歷整數(shù)a的所有因數(shù)時，-b也遍歷整數(shù)a的所有因數(shù)。(2) 當(dāng)b遍歷整數(shù)a的所有因數(shù)時， q a/b也遍歷整數(shù)a的所有因數(shù)。整除的性質(zhì)：2. 0是任何非零整數(shù)的倍數(shù)，1是任何整數(shù)的因數(shù)，任何非零整數(shù)a是自身的倍數(shù)，也是自身的因數(shù)。 設(shè)b0，00b，b|0； 對任意整數(shù)a，aa1， 1|a； 設(shè)a 0，則 a|a 。整除的性質(zhì)：3. 設(shè)c 0，且c|1 (1qc)，則c1。4. 設(shè)a，b是整數(shù)， b0。若b|a，則 b|(-a) , (-b)|a , (-b)|(-a) , b | | a | , | b | | a, |

17、b | | | a | 。5. 設(shè)a，b ，c是三個整數(shù)， b0 ， c0 。若c|b， b|a，則 c|a ，即，整除具有傳遞性。整除的性質(zhì)：6.設(shè)a，b ，c是三個整數(shù)，c0 。若c|a， c|b，則 c|(ab) 。7.設(shè)a，b ，c是三個整數(shù)，c0 。若c|a， c|b，則 對任意整數(shù)s和t，有c|(satb) 。8. 設(shè)a，b ，c是三個整數(shù)， c0 ， c|a， c|b。如果存在整數(shù) s 和 t 使得 satb1，則 c1。整除的性質(zhì)：9.設(shè)a1，a2 ，an，c都是整數(shù)，c0 。 若c| a1 ， c| a2 ， c| an ，則對任意整數(shù)s1， s2 ，sn， c|(s1a1+

18、 s2a2+ snan) 。10.設(shè)a，b 是整數(shù)，a0 ，b0 。若a|b， b|a， 則 ab 。課堂練習(xí)證明：7.設(shè)a，b ，c是三個整數(shù)，c0 。若c|a， c|b，則 對任意整數(shù)s和t，有c|(satb) 。5. 設(shè)a，b ，c是三個整數(shù)， b0 ， c0 。若c|b， b|a，則 c|a ，即，整除具有傳遞性。定義2 設(shè)整數(shù)n 0 ，1。如果除了顯然因數(shù)1和n外，n 沒有其它因數(shù)，那么，n叫素數(shù)(或質(zhì)數(shù)或不可約數(shù))，否則n叫合數(shù)。若整數(shù)n 0 ，n為素數(shù)或合數(shù)時，-n也為素數(shù)或合數(shù)。一般素數(shù)總是指正整數(shù)。通常用p表示。素數(shù)：設(shè)p是奇素數(shù)，如果(p1)/2也是素數(shù)，則素數(shù)p叫安全素數(shù)

19、。如p5， p7， p11， p23，p47，安全素數(shù)在RSA密碼系統(tǒng)中有應(yīng)用。定理6. 設(shè)n 為正合數(shù)，p是n的一個大于1的最小正因數(shù)，則 p 一定是素數(shù)，且 。證明 反證法。如果p不是素數(shù)，則存在整數(shù)q (1 q p)使得q | p，但p | n，根據(jù)定理一，有q | n。這與p是n的最小正因數(shù)矛盾。所以，p 是素數(shù)。 因為n 是正合數(shù)，所以存在整數(shù)n1使得 n pn1 ，1 p n1 n 因此， p 2 pi，i1, 2, , k，所以n一定是合數(shù)。根據(jù)定理6，n的大于1的最小正因數(shù)p是素數(shù)。因此，p是p1, p2, , pk中的某一個，即存在j, 1 j k，使得ppj。根據(jù)定理3，有

20、p|(n- p1 p2 pk), 即p|1。得到矛盾。故存在有無窮多個素數(shù)。歐幾里得(Euclid)除法最小非負(fù)余數(shù)：定理9(歐幾里得除法). 設(shè)a, b 是兩個整數(shù)，其中b0。則存在唯一一對整數(shù)q, r 使得 a bq + r，0 r b。定義3. 稱上式中的q為a被 b 除所得的不完全商，稱r 為a被 b 除所得的余數(shù)(最小非負(fù)余數(shù))。a bq + r，0 r 0。則存在唯一一對整數(shù)q, r 使得 a bq + r，0 r 0。則存在唯一一對整數(shù)q, r 使得 a bq + r，0 r b。, -3b,-2b,-b, 0, b, 2b, 3b, qb (q+1)ba設(shè)a 落在區(qū)間qb， (

21、q+1)b)中。因此，存在一個整數(shù)q使得 qb a (q+1)b， 即 0 a-bq b。令 ra-bq，則有 a bq + r，0 r 0。則存在唯一一對整數(shù)q, r 使得 a bq + r，0 r b。 (1)證明.唯一性. 假設(shè)還有一對整數(shù)q1, r1 也滿足： a bq1 + r1，0 r1 0，整數(shù)q, r 使得 a bq + r，0 r b。則 b|a的充要條件是a被b除所得的余數(shù)r0。定義4. 設(shè)x是實數(shù)，稱x的整數(shù)部分為小于或等于x的最大整數(shù)，記成x，這時有x x 0。則對任意整數(shù)c，存在唯一一對整數(shù)q, r 使得 a bq + r，c r bc。 (4)例如：設(shè)a 15， b

22、 6，a bq + r，c r 0。則對任意整數(shù)c，存在唯一一對整數(shù)q, r 使得 a bq + r，c r bc。證明.存在性. 考慮整數(shù)序列： , -3b+c, -2b+c, -b+c, c, b+c, 2b+c, 3b+c, , -3b+c, -2b+c, -b+c, c, b+c, 2b+c, 3b+c, 序列的各項把實數(shù)軸劃分成長度為b的區(qū)間，, -3b+c, -2b+c, -b+c, c, b+c, 2b+c, 3b+c, a一定落在其中的一個區(qū)間中。設(shè)a 落在區(qū)間qb+c， (q+1)b+c)中。因此，存在一個整數(shù)q使得 qb+c a (q+1)b+c， 即 c a-bq b+c

23、。令 ra-bq，則有 a bq + r，c r 0。則對任意整數(shù)c，存在唯一一對整數(shù)q, r 使得 a bq + r，c r bc。 (4) 假設(shè)還有一對整數(shù)q1, r1 也滿足： a bq1 + r1，c r1 0。則對任意整數(shù)c，存在唯一一對整數(shù)q, r 使得 a bq + r，c r bc。 (4)例如：設(shè)a 15， b 6，a bq + r，c r bc。 取 c 0 ：r ，q ， c 3：r ， q ， c 86：r ， q ， c 100 ：r ，q ，323212871999例如：設(shè)a 230， b 7，a bq + r，c r bc。 取 c 0 ：r ，q ， c 1：r

24、 ， q ， c 6：r ， q ， c 100 ：r ，q ，63263233 14799歐幾里得除法一般余數(shù)1. 當(dāng)c0 時，0 r b，這時稱r為最小非負(fù)余數(shù)。2. 當(dāng)c1時，1 r b，這時稱r為最小正余數(shù)。3. 當(dāng)cb+1時，b+1 r 0，這時稱r為最大非正余數(shù)。4. 當(dāng)cb時，b r 0。則對任意整數(shù)c，存在唯一一對整數(shù)q, r 使得 a bq + r，c r bc。 (4)5. (i) 當(dāng) b2k, ck時, 有 b/2 k r k b/2， (ii) 當(dāng) b2k, ck+1時, 有 -b/2 k r k b/2， (iii) 當(dāng) b2k+1, c k時，有 b/2 (b-1)

25、/2 k r k+1 (b+1)/2，即 b/2 (b-1)/2 k r (b-1)/2 0。則對任意整數(shù)c，存在唯一一對整數(shù)q, r 使得 a bq + r，c r 0，如果b|a，則(a, b )b。 5. 設(shè)a1, a2, , an 是 n個不全為零的整數(shù)，則 (i) a1, a2, , an與|a1|, |a2|, , |an|的公因數(shù)相同。 (ii) (a1, a2, , an)(|a1|, |a2|, , |an| )。6. 設(shè)a, b 是兩個整數(shù)，則 (a, b )(a, b )(a, b ) (| a |, | b |) 。4.設(shè)p是一個素數(shù)， a是整數(shù)，如果p | a，則p與

26、a互素。最大公因數(shù)的性質(zhì)：7. 設(shè) b 是任一正整數(shù)，則(0, b )b。8.定理1.3.3 設(shè)a, b, c是三個不全為零的整數(shù)。如果 a bq + c, 其中q是整數(shù)，則有(a, b) (b, c)。9.定理1.3.4 設(shè)a, b 是任意兩個正整數(shù)，則(a, b )rn，其中rn是廣義歐幾里得除法中最后一個非零余數(shù)，有 (a, b)(r1, r2)(r2, r3)(rn-1, rn) (rn, 0) rn10. 定理1.3.5 設(shè)a, b是任意兩個正整數(shù)，則存在整數(shù)s和t使得：sa+tb (a, b) 。Bzout(貝祖)等式。最大公因數(shù)的性質(zhì)：11定理1.3.7 設(shè)a, b是任意兩個正整

27、數(shù),則 對于 j 0, 1, 2, n，sj 和 tj 歸納地定義為 其中 rj ， qj 分別是廣義歐幾里得除法中的余數(shù)和不完全商。j 0, 1, 2, n最大公因數(shù)的性質(zhì)：最大公因數(shù)的性質(zhì)：12.定理1.3.8 整數(shù)a, b互素的充分必要條件是存在整數(shù)s, t使得 sa + tb 1 13. 設(shè)四個整數(shù)a, b, c, d 滿足關(guān)系式：ad bc1 則(a, b)1, (a, c)1, (d, b)1, (d, c)1。最大公因數(shù)的性質(zhì)：14.定理1.3.9 設(shè)a, b是任意兩個不全為零的整數(shù),d 是正整數(shù),則 d 是整數(shù)a, b的最大公因數(shù)的充要條件是： (i) d|a, d|b； (i

28、i) 若e|a, e|b, 則 e|d。 最大公因數(shù)的性質(zhì)：15.定理1.3.10 設(shè)a, b是任意兩個不全為零的整數(shù), (i) 若 m 是任一正整數(shù),則(ma, mb)m (a, b). (ii) 若非零整數(shù) d 滿足d|a, d|b, 則特別的：最大公因數(shù)的性質(zhì)：17.定理1.3.12 設(shè) a1, a2, , an，c為正整數(shù), 如果 (ai , c) 1, 1in,則 (a1 a2 an，c) 1.16.定理1.3.11 設(shè)a, b, c是三個整數(shù), 且b0, c0, 如果 (a, c)1, 則(ab, c) (b, c)最大公因數(shù)的性質(zhì)：18.定理1.3.13 設(shè)a, b和u, v都是

29、不全為零的整數(shù),如果a qu + rv， b su + tv，其中q , r，s , t是整數(shù),且qt - rs 1，則 (a, b ) (u, v ) 。最大公因數(shù)在可逆變換下的不變性。最大公因數(shù)的性質(zhì)： 19.引理1.3.2 設(shè)a,b是兩個正整數(shù),則 和 的最大公因數(shù)是 。 20.定理1.3.16 設(shè)a,b是兩個正整數(shù),則正整數(shù) 和 互素的充要條件是 a 和 b 互素.最大公因數(shù)的性質(zhì)：21.定理1.4.1 設(shè) a, b，c是三個整數(shù),且c0。如果 c|ab，(a , c) 1, 則 c|b.22.定理1.4.2 設(shè)p 是素數(shù),若 p|ab,則 p|a或p|b 。23.定理1.4.3 設(shè)

30、a1, a2, , an 是 n 個整數(shù),p 是素數(shù),若 p|a1 a2an,則 p 一定整除某一個ak, 1kn。最大公因數(shù)的性質(zhì)證明：2.設(shè)a, b 是兩個整數(shù)，則(a, b )(b, a )。3.設(shè)a, b 是兩個整數(shù)，b 0，如果b|a，則(a, b )b。最大公因數(shù)的性質(zhì)證明：4.設(shè)p是一個素數(shù)， a是整數(shù)，如果p | a，則p與a互素。證明. 設(shè)(p, a )d，則有d | p， d | a。 因為p是素數(shù)，所以由d | p， 有d1或dp。 若dp，由d | a ，有p | a，這與假設(shè)p | a矛盾。因此，d1，即(p, a )1，結(jié)論成立。最大公因數(shù)的性質(zhì)證明： 5. 設(shè)a1

31、, a2, , an 是 n個不全為零的整數(shù)，則 (i) a1, a2, , an與|a1|, |a2|, , |an|的公因數(shù)相同。 (ii) (a1, a2, , an)(|a1|, |a2|, , |an| )。6. 設(shè)a, b 是兩個整數(shù)，則 (a, b )(a, b )(a, b ) (| a |, | b |) 。7. 設(shè) b 是任一正整數(shù)，則(0, b )b。8.定理1.3.3 設(shè)a, b, c是三個不全為零的整數(shù)。如果 a bq + c, 其中q是整數(shù)，則有(a, b) (b, c)。最大公因數(shù)的性質(zhì)：證明. 設(shè)d(a, b )，d(b, c )，則d|a, d|b。所以 d

32、| (a(q)b), 即d|c。因而d是b，c的公因數(shù)。從而d d。又d |b, d |c，可得d | (bq c), 即d | a 。因而d是a，b的公因數(shù)。從而d d。 所以dd，即(a, b) (b, c)。例10：設(shè)a1859，b1573，求(a, b) 因為185911573286，所以 (1859, 1573) (1573, 286) 又所以 (1573, 286) (286, 143) 28621430 ，所以 (286, 143) (143, 0) 143所以 (1859, 1573) 143利用定理3 可計算兩個整數(shù)a, b的最大公因數(shù)。課堂練習(xí)：設(shè)

33、a1071，b462，求(a, b)解 10712462147 462314721 147721 所以 (1071, 642) 21令r0 a，r1 b， 反復(fù)運(yùn)用歐幾里得除法(稱為廣義歐幾里得除法)可得：最大公因數(shù)的求法：廣義歐幾里得除法設(shè)a, b 是任意兩個正整數(shù)，求a, b 的最大公因數(shù) d(a, b )。r0 r1q1+r2, 0 r2 r1r1r2q2+r3,0 r3 r2 rk-2rk-1qk-1+rk,0 rk rk-1 rn-2rn-1qn-1+rn,0 rn rn-1rn-1rnqn + rn+1 , rn+10 r0 a，r1 b，廣義歐幾里得除法：0 根據(jù)定理1.3.3有

34、 (a, b)(r1, r2)(r2, r3)(rn-1, rn) (rn, 0) rn9.定理1.3.4 設(shè)a, b 是任意兩個正整數(shù)，則(a, b )rn，其中rn是廣義歐幾里得除法中最后一個非零余數(shù)，有 (a, b)(r1, r2)(r2, r3)(rn-1, rn) (rn, 0) rn (a, b) (r1, r2) (r2, r3) (rn-1, rn) (rn, 0) rn例：設(shè)a169，b121，求 (a, b) 用廣義歐幾里德除法求兩個整數(shù)的最大公因數(shù)， 可以用：（1）最小非負(fù)余數(shù)：（2）絕對值最小余數(shù)：（3）最小非正余數(shù)：求兩個整數(shù)的最大公因數(shù)的過程：（1）將求兩個整數(shù)的最

35、大公因數(shù)轉(zhuǎn)化為求兩個非負(fù)整數(shù)的最大公因數(shù)；（2）運(yùn)用廣義歐幾里得除法，根據(jù)定理1.3.3 ，將求兩個正整數(shù)的最大公因數(shù)轉(zhuǎn)化為求兩個較小非負(fù)整數(shù)的最大公因數(shù)(用較小的數(shù)除較大的數(shù)，可考慮不同余數(shù))；（3）運(yùn)用廣義歐幾里得除法，將求兩個正整數(shù)的最大公因數(shù)轉(zhuǎn)化為求0和一個正整數(shù)的最大公因數(shù)；例12：設(shè)a1859，b1573，求(a, b) 解 由定理1 (1859, 1573) (1859, 1573) 運(yùn)用廣義歐幾里得除法，有 1859115732862862143 根據(jù)定理4 (1859, 1573) 143課堂練習(xí)：設(shè)a24871，b3468，求(a, b)解 運(yùn)用廣

36、義歐幾里得除法，有 2487173468595 34685595493 5951493 102 493410285 10218517 85517 所以 (24871, 3468) 17課堂練習(xí)：設(shè)a24871，b3468，求(a, b)解 運(yùn)用廣義歐幾里得除法，有 2487173468595 34686595 102 5956102 17 102617 所以 (24871, 3468) 1710. 定理1.3.5 設(shè)a, b是任意兩個正整數(shù)，則存在整數(shù)s和t使得：sa+tb (a, b) 。Bzout(貝祖)等式。 最大公因數(shù)的性質(zhì)證明：r0 r1q1+r2, 0 r2 r1r1r2q2+r3

37、,0 r3 r2 rk-2rk-1qk-1+rk,0 rk rk-1 rn-2rn-1qn-1+rn,0 rn rn-1rn-1rnqn + rn+1, rn+10 (a, b) rn令 r0 a，r1 b。證明：由廣義歐幾里德除法可得： 削去 rn1, rn2, , r3, r2, 可找到 s 和 t 使得： sa+tb (a, b) 。 例：a737，b635，求 s 和 t 使得 sa+tb (a, b) 。 解：7371635102， 635 6 102 23， 10242310， 232103， 10331， 331，102737 163523 635 610210102 42332

38、3 210110 33 解：110 33 (102 423)3(23 210) 1027 236 10 1027 236 (102 423) 7 10231 23 7 10231 (635 6103) 193 102 31 635 193 (737 1635) 31 635 193 737 224635 所以 s 193， t 224，使得 193 737(224) 6351。課堂練習(xí)：設(shè)a24871，b3468，求(a, b)課堂練習(xí)：a24871，b3468，求 s 和 t 使得 sa+tb (a, b) 。課堂練習(xí)：設(shè)a24871，b3468，求(a, b)解 運(yùn)用廣義歐幾里得除法，有

39、2487173468595 34685595493 5951493 102 493410285 10218517 85517 所以 (24871, 3468) 17課堂練習(xí)：設(shè)a24871，b3468，求(a, b)解 運(yùn)用廣義歐幾里得除法，有 2487173468595 34686595 102 5956102 17 102617 所以 (24871, 3468) 17課堂練習(xí)：a24871，b3468，求 s 和 t 使得 sa+tb (a, b) 。解 運(yùn)用廣義歐幾里得除法，有 2487173468595346855954935951493 10249341028510218517 85

40、517(24871, 3468) 171710218517102 1(4934102) 5102 1493175(595 1493)1493 5595 6493175595 6 (3468 5595) 35595 634681735 (2487173468) 63468 3524871 2513468s35, t 251課堂練習(xí)：a24871，b3468，求 s 和 t 使得 sa+tb (a, b) 。17 610259517 6(65953468) 595 35595 634681735(24871 73468)63468 3524871 251493s35, t 251解 運(yùn)用廣義歐幾里

41、得除法，有 248717346859534686595 1025956102 17102617(24871, 3468) 1711定理1.3.7 設(shè)a, b是任意兩個正整數(shù),則 對于 j 0, 1, 2, n，sj 和 tj 歸納地定義為 其中 rj ， qj 分別是廣義歐幾里得除法中的余數(shù)和不完全商。j 0, 1, 2, n最大公因數(shù)的性質(zhì)：jsjtjq j+1r j+1-3a-110b-101q0r00s0t0q1r11s1t1q2r2n-2sn-2tn-2qn-1rn-1n-1sn-1tn-1qnrn-2nsntnqn+1rn+1=0對于 j 0, 1, 2, , n 最大公因數(shù)的性質(zhì)證

42、明：12.定理1.3.8 整數(shù)a, b互素的充分必要條件是存在整數(shù)s, t 使得 sa + tb 1 。13. 設(shè)四個整數(shù)a, b, c, d 滿足關(guān)系式：ad bc1 則(a, b)1, (a, c)1, (d, b)1, (d, c)1。作業(yè)：p49：24， 25， 28(3)，29(1,2)，32(4)，最大公因數(shù)的性質(zhì)證明：14.定理1.3.9 設(shè)a, b是任意兩個不全為零的整數(shù),d 是正整數(shù),則 d 是整數(shù)a, b的最大公因數(shù)的充要條件是： (i) d|a, d|b； (ii) 若e|a, e|b, 則 e|d。 證明：若d 是整數(shù)a, b的最大公因數(shù)，則(i) 成立。由定理1.3.

43、7，存在整數(shù)s和t使得 sa+tb (a, b) d 。因此當(dāng)e|a, e|b 時， 有 e| sa+tb d。即(ii) 成立。最大公因數(shù)的性質(zhì)證明：14.定理1.3.9 設(shè)a, b是任意兩個不全為零的整數(shù),d 是正整數(shù),則 d 是整數(shù)a, b的最大公因數(shù)的充要條件是： (i) d|a, d|b； (ii) 若e|a, e|b, 則 e|d。 證明：反之，設(shè)(i), (ii)成立，那么， (i) 說明 d是整數(shù)a, b的公因數(shù)。(ii)因為e|d時，有|e|d。說明d是整數(shù)a, b的公因數(shù)中的最大數(shù)。因此，d 是整數(shù)a, b的最大公因數(shù) 最大公因數(shù)的性質(zhì)證明：15.定理1.3.10設(shè)a, b

44、是任意兩個不全為零的整數(shù), (i) 若 m 是任一正整數(shù),則(am, bm)(a, b)m. (ii) 若非零整數(shù) d 滿足d|a, d|b, 則特別的：證 令 d(ab,c), d(b,c)。我們有 d|b, d|c, 進(jìn)而 d|ab, d|c。根據(jù)定理1.3.9, 我們得到 d|d.反過來,因為(a,c)1,根據(jù)定理1.3.8,存在整數(shù) s,t 使得 sa + tc 1兩端同乘 b, 得到s(ab) + (tb)c b根據(jù)定理1.1.3,由d|ab,d|c,我們得到d|s(ab)+(tb)c,即d|b。同樣,根據(jù)定理1.3.9,我們得到d|d 。故 d d。 最大公因數(shù)的性質(zhì)證明： 16.

45、定理1.3.11 設(shè)a, b, c是三個整數(shù), 且 b0, c0, 如果 (a, c)1, 則(ab, c) (b, c)最大公因數(shù)的性質(zhì)證明：17.定理1.3.12 設(shè) a1, a2, , an，c為正整數(shù), 如果 (ai , c) 1, 1in,則 (a1 a2 an，c) 1.證明：對n作數(shù)學(xué)歸納法。n2 時, 就是定理1.3.11 假設(shè)n1 時,命題成立。即 (a1 a2 an1，c) 1 對于n, 根據(jù)歸納假設(shè) (a1 a2 an1 , c) 1, 再根據(jù)(an , c) 1, 及定理1, 得到既命題對所有的n成立。最大公因數(shù)的性質(zhì)證明：18.定理1.3.13 設(shè)a, b和u, v都

46、是不全為零的整數(shù),如果a qu + rv， b su + tv，其中q , r，s , t是整數(shù),且qt - rs 1，則 (a, b ) (u, v ) 。最大公因數(shù)在可逆變換下的不變性。證 令 d(a, b), d(u,v)，則 d|u, d|v, 由定理1.1.3得 d| qu + rv a, d| su + tv b。因而d|d.又由假設(shè)可得uta + (-r)b， v(-s)a + qb同理可得得到d|d 。故 d d。 最大公因數(shù)的性質(zhì)證明： 19.引理1.3.2 設(shè)a,b是兩個正整數(shù),則 和 的最大公因數(shù)是 。 20.定理1.3.16 設(shè)a,b是兩個正整數(shù),則正整數(shù) 和 互素的充

47、要條件是 a 和 b 互素.引理1 設(shè)a, b是兩個正整數(shù).若a bq + r, 其中 r 是 a 被 b 除的最小正余數(shù)(1 r b) 。則 2a1 被2b1除的最小正余數(shù)是2r1 (1 2r1 2b1) 。證 當(dāng)a 0是a1, a2, , an的最大公因數(shù)當(dāng)且僅當(dāng)： (1) d|a1, d|a2, , d| an, (最大公因數(shù)是每個數(shù)的因數(shù)) (2) 若e|a1, e|a2, , e| an ，則e|d 。(每個公因數(shù)都整除最大公因數(shù))大整數(shù)運(yùn)算大整數(shù)存儲由于大整數(shù)的位數(shù)太多，我們首先要做的是把它“拆”開來，存放在若干個地方，然后建立不同存儲地址之間的聯(lián)系。對于大整數(shù)1112223334

48、445用一維數(shù)組存儲:001112223334445用鏈表存儲：45head 44332322111用數(shù)組存儲大整數(shù)(12345678901234567890)123456789012345678901234567890123456789012345678901234567890用數(shù)組存儲大整數(shù)時，每一個數(shù)組元素表示多位整數(shù),時空效率要比每一個數(shù)組元素表示一位整數(shù)好。每個數(shù)組元素表示5位整數(shù)時最好；取6位時，相乘可能溢出。大整數(shù)的加法運(yùn)算+468818814582811000714890203010910070148901913001123456789012345678900097661470

49、00079625679800大整數(shù)的乘法運(yùn)算3456789525679823160489653710338765864197375+88769663002109895=93109878+93=77379856+77=55659834+55=33876795=63656778+63=52896756+52=38046734+38=23162595=23752578+23=19732534+14=8642556+19=1419作業(yè)：p50：35， 36， 37，課外練習(xí)：1. 用廣義歐幾里得除法求兩個整數(shù)的最大公因數(shù)。2. 用定理1.3.7求s和t使得：sa+tb (a, b) 。 要求對任意整數(shù)

50、給出結(jié)果。定義 1 設(shè) a1, a2, , an是 n 個整數(shù)，若 D 是這 n個數(shù)的倍數(shù)，則 D 叫做這 n 個數(shù)的一個公倍數(shù)。 a1, a2, , an 的所有公倍數(shù)中的最小正整數(shù)叫做最小公倍數(shù)。記作 a1, a2, , an。若 D 是a1, a2, , an最的小公倍數(shù)，則 D a1, a2, , an。1.4.2 最小公倍數(shù)例 14和21的公倍數(shù)為 42, 84, ， 14和21的最小正公倍數(shù)為 42 。最小公倍數(shù)的性質(zhì)：1 設(shè) a1, a2, , an是 n 個整數(shù)，則整數(shù) D 是a1, a2, , an最的小公倍數(shù)，即 D a1, a2, , an當(dāng)且僅當(dāng) （i） ai | D,

51、 1in; (最小公倍數(shù)是每個數(shù)的倍數(shù)) (ii) 若 ai | D, 1 in, 則 D | D。 (每個公倍數(shù)都能被最小公倍數(shù)整除)最小公倍數(shù)的性質(zhì)：2. a, b的最小公倍數(shù) D a, b 是集合c | cZ, a|c, b|c 中的最小正整數(shù)。類似的： a1, a2, , an的最小公倍數(shù) D a1, a2, , an 是集合 c | cZ, ai|c, 1in中的最小正整數(shù)。最小公倍數(shù)的性質(zhì)：3. 定理 1.4.4 設(shè) a, b 是兩個互素的正整數(shù)(a , b)1,則 (i) 若a | D, b | D, 則 a b | D; (ii) a, b a b.4. 設(shè)p，q是兩個不同的素

52、數(shù)，則p, q p q。5. (50頁第39題)設(shè)a, b是任意兩個不全為零的整數(shù)若m是任一正整數(shù)，則m a, m bm a, b 。最小公倍數(shù)的性質(zhì)：6. 定理 1.4.5 設(shè)a, b 是兩個正整數(shù)，則 (i)若 a|D, b|D, 則a, b|D (ii) 即 a, b (a, b) a b 7. 定理1.4.6 設(shè)a1, a2, , an是n個整數(shù)。令 則最小公倍數(shù)的性質(zhì)：8. 定理1.4.7 設(shè)a1, a2, , an是n個正整數(shù)。如果 則最小公倍數(shù)的性質(zhì)證明：3. 定理 1.4.4設(shè) a, b 是兩個互素的正整數(shù)(a , b)1,則 (i) 若a| D, b| D, 則 a b |

53、D; (ii) a, b a b. 證明： 設(shè) a| D ，則D a k。又b| D, 即 b| a k, 由(a, b)1, 根據(jù)定理1.3.11的推論，得到b|k。 因此 k bt, 進(jìn)而D abt。故a b| D 。(i)得證。 即 a b 是a, b 的公倍數(shù)。又由 (i) 知，對a b的任一公倍數(shù)D ，都有a b D 。所以a b是a, b 的公倍數(shù)中最小正整數(shù), 故a, ba b。5. (50頁第39題)設(shè)a, b是任意兩個不全為零的整數(shù)若m是任一正整數(shù)，則am, bma, bm。. 最小公倍數(shù)的性質(zhì)證明：證明:設(shè) L a, b，則 a L， b L，進(jìn)而am Lm， bm Lm，

54、即Lm是am, bm的公倍數(shù)。所以am, bm Lm a, bm。反之，設(shè)L am, bm，及L k1am ， L k2bm ，由此知，5. (50頁第39題)設(shè)a, b是任意兩個不全為零的整數(shù)若m是任一正整數(shù)，則am, bma, bm。最小公倍數(shù)的性質(zhì)：5. (50頁第39題)設(shè)a, b是任意兩個不全為零的整數(shù)若m是任一正整數(shù)，則am, bma, bm。. 最小公倍數(shù)的性質(zhì)： 最大公因數(shù)的性質(zhì)：15.定理1.3.10 設(shè)a, b是任意兩個不全為零的整數(shù), (i) 若 m 是任一正整數(shù),則(am, bm)(a, b)m. (ii) 若非零整數(shù) d 滿足d|a, d|b, 則最小公倍數(shù)的性質(zhì)證明

55、：6. 定理 1.4.5 設(shè)a, b 是兩個正整數(shù)，則 (i)若 a|D, b|D, 則a, b|D (ii) 即 a, b (a, b) a b 證明：先證明(ii)成立 令d (a，b), 根據(jù)定理1.3.10，有根據(jù)定理1.4,4， 。進(jìn)而，即(ii)成立。(?)證明：證明(i)成立 由得到，從而，即(i)成立。根據(jù) (?)定理1.4.4例 計算最小公倍數(shù) 1400，2100。 解 因為 (1400, 2100) 700 所以最小公倍數(shù)的性質(zhì)證明：例 5 計算最小公倍數(shù)12，15，21，35。 解 因為 12, 15 60 60, 21 420 420, 35 420所以最小公倍數(shù)12，

56、15，21，35420.最小公倍數(shù)的性質(zhì)證明：8. 定理1.4.7 設(shè)a1, a2, , an是n個正整數(shù)。如果 則1.5 整數(shù)分解定理 1.5.1 (整數(shù)分解定理)給定正合數(shù) n 1。如果存在整數(shù)a，b使得 n | a2b2 ，n | ab ，n | ab ，則(n，ab)和(n，ab)都是n的真因數(shù)(除1和本身以外的因數(shù))。定理 1.5.1 (整數(shù)分解定理)給定正合數(shù) n 1。如果存在整數(shù)a，b使得 n | a2b2 ，n | ab ，n | ab ，則(n，ab)和(n，ab)都是n的真因數(shù)。證 若(n，ab)不是n的真因數(shù)，則(n，ab)為1或n 。若(n，ab) 1，由n | a2b

57、2 知n | (ab) (a b)，得n | (a b)，與假設(shè)矛盾。若(n，ab) n ，推出n | (ab) ，與假設(shè)矛盾。故(n，ab)是n的真因數(shù)。同理，(n，ab) 是n的真因數(shù)。1.6 算術(shù)基本定理定理 1.6.1 (算術(shù)基本定理)任一整數(shù) n 1都可以表示成素數(shù)的乘積，且在不考慮乘積順序的情況下，該表達(dá)式是唯一的。 即 n p1 p2 ps , p1 p2 ps (1)其中 pi 是素數(shù)，并且若 n q1 q2 qt , q1 q2 qt其中 qi 是素數(shù)，則 t s, qi pi ，1 i t.證 對 n 用數(shù)學(xué)歸納法證明： n p1 p2 ps , p1 p2 ps (1)

58、當(dāng)n2時，(1)式成立。 假設(shè)對于小于n的正整數(shù)，(1)式成立。 對于正整數(shù) n， 若 n 是素數(shù)，則(1)式對 n 成立。 若 n 是合數(shù)，則存在正整數(shù) n1, n2 使得 n n1 n2, 1 n1 n, 1 n2 1 可以唯一地表示成其中 pi pj ( i 1 ，且有標(biāo)準(zhǔn)分解式則 d 是 n 的正因數(shù)當(dāng)且僅當(dāng) d 有因數(shù)分解式：例 寫出整數(shù)21，100的所有正因數(shù)。解 213 7 ， 21 的所有正因數(shù)為：30 70 ， 31 70 ， 30 71 ， 31 71 1, 3, 7, 21例 寫出整數(shù)21，100的所有正因數(shù)。解 100 22 52 ， 100 的所有正因數(shù)為：20 50

59、 ， 20 51 ， 20 52 ， 21 50 ， 21 51 , 21 52 ， 22 50 ， 22 51 ， 22 52 1, 5, 25, 2, 10, 50, 4, 20, 100 例 3 設(shè)正整數(shù) n 有因數(shù)分解式則 n 的正因數(shù)個數(shù)證明：設(shè) d 是正整數(shù) n 的正因數(shù)，根據(jù)定理3，因為 1 的變化范圍是從 0 到 1 ，共有1 1個值，因為 2 的變化范圍是從 0 到 2 ，共有1 2個值，因為 s 的變化范圍是從 0 到 s ，共有1 s個值， 所以 n 的因數(shù)個數(shù)為定理 1.6.4 設(shè)a，b是兩個正整數(shù)，且有素因數(shù)分解則 a 和 b 的最大公因數(shù)和最小公倍數(shù)有因數(shù)分解：證明

60、： 根據(jù)定理1.6.3，整數(shù)滿足最大公因數(shù)的定義，所以同理，整數(shù)滿足最小公倍數(shù)的定義，所以例：計算120，150，210，35的最大公因數(shù)和 最小公倍數(shù) 。解：12023 3 5 ， 150 2 3 52 2102 3 5 7 ， 35 5 7根據(jù)定理1.6.4， (120, 150)2 3 5 30； (30, 210) 2 3 5 30 (30, 35)5 所以 (120, 150, 210, 35) 5 12023 3 5 ， 150 2 3 52 2102 3 5 7 ， 35 5 7同樣，根據(jù)定理1.6.4 ， 120, 15023 3 52 600， 600, 210 23 3 5