第1章-整数的可除性课件

1、信息安全数学基础 周杰课程简介教学方式：理论课教学总学时：48考核方式：考试(70%)+(作业+平时) (30%)课程学分：3先修课程：无 教材、参考书：陈恭亮 信息安全数学基础 简明信息安全数学基础 潘承洞,潘承彪 初等数论后续课程：密码学与安全协议密码学简介 密码学 Cryptology维基百科：研究如何隐密地传递信息的学科 是指对信息以及其传输的数学性质的研究，是数学和计算机科学的分支，和信息论密切相关。Wo ent out nh u ote ll orm dic e kodw? yemiiWould you like to come to dinner with me?密码学简介 密码

2、学 Cryptology百度百科：研究编制密码和破译密码技术的科学 研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为解码学，总称密码学密码学简介 密码学 Cryptology 密码学是信息安全中的相关议题，如认证、访问控制的核心。密码学的首要目的是隐藏信息的涵义，并不是隐藏信息的存在。 密码学已被应用在日常生活：包括自动柜员机的芯片卡、电脑使用者存取密码、电子商务等等。密码学简介 明文(plaintext)任何人都读得懂的文字密文(encrypted; cipher text)用特殊方法使明文内容变得混乱，使得只有持有“密钥”的人才能恢复

3、出明文。Encrypt / decrypt加密 / 解密密码学简介 明文(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?保密系统模型 保密系统模型图 搭线信道 搭线信道 非法 (主动攻击) (被动攻击) 密码分析员m 接入者 c (窃听者) 信 源m 加密器 c 解

4、密器m 接收者mc=Ek1(m) 信道m=D k2(c) k1 k2 密钥源 密钥源 k1 密钥信道 k2 m明文密文监听、截取、更改、增加加密密钥解密密钥加密方法解密方法明文机密性防止窃听完整性内容不可被更改鉴定性确定信息确实是由真正的发送者所传送不可否认性发送方在事后不可否认其传送的消息密码学主要目标 密码学历史 密码学的历史已有四千多年 早期的密码学主要作为军事用途。Caesar Cipher (凯撒密码)(2千年前罗马)每个字母用其前(后)面的字母替代A Z; B A; 一般形式，Caesar Cipher 中字母移动的位数可以为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(数字)33(标点符号)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 当 y 90yy 当 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凯撒密码的数学原理明文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 当 y 65xx 当 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阿拉伯人发明频率攻击方法(9世纪)第一次世界大战无线电的发明，电码本。第二次世界大战以机械代替人手的加密方法。密码学历史 德国的洛伦兹密码机，加密机密邮件上世纪70年代中期, 首次出现了现代分组密码DES1976年，Diffie和Hellman 在“密码学新方向”一文中首次提出公钥密码的思想使用两个密钥：公钥、私钥加密和解密不是对称的是对对称密码的重要补充DiffieHellman密钥交换方法Di

13、ffie W, Hellman M E. New directions in cryptography J. IEEE Transactions on Information Theory, 1976,22(6): 644654 密码学历史 1978年，由MIT的 Rivest, Shamir & Adleman给出一种公钥密码算法RSA算法最著名的且被广泛应用的公钥加密体制 利用数论的方法明文、密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数。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. 密码学历史 2002年他们被授予图灵奖（Turing Award）： “授予Ronald L. Rivest, Adi Shamir, Leonard M. Adleman图灵奖以表彰其使得公钥密码技术在实际中应用的创造性贡献。” RSA算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制。 Rivest, R. L., Shamir, A., Adlem

15、an, L. AShamir2008年4月24日下午 世界著名密码学家、图灵奖获得者以色列Weizmann科学院教授 Adi Shamir教授做客清华论坛2010年5月山东大学授予Adi Shamir教授名誉博士学位 第一章 整数的可除性 1.1 整除的概念 欧几里德除法 定义1 设a，b是任意两个整数，b0。若有整数q使 abq，就称b整除a，或a被b整除，记作b|a，并把b叫a的因数，a叫b的倍数。q也整除a，或a被q整除，即有q|a，并且q是a的因数，a也是q的倍数。记做整数：Z, -2, -1, 0, 1, 2, 定义1 如果使得abq的整数q不存在，称b不整除a，或a不能被b整除。记

16、作b | a。整除的性质：1. 如果b整除a， 即abq。则(1) 当b遍历整数a的所有因数时，-b也遍历整数a的所有因数。(2) 当b遍历整数a的所有因数时， q a/b也遍历整数a的所有因数。整除的性质：2. 0是任何非零整数的倍数，1是任何整数的因数，任何非零整数a是自身的倍数，也是自身的因数。 设b0，00b，b|0； 对任意整数a，aa1， 1|a； 设a 0，则 a|a 。整除的性质：3. 设c 0，且c|1 (1qc)，则c1。4. 设a，b是整数， b0。若b|a，则 b|(-a) , (-b)|a , (-b)|(-a) , b | | a | , | b | | a, |

17、b | | | a | 。5. 设a，b ，c是三个整数， b0 ， c0 。若c|b， b|a，则 c|a ，即，整除具有传递性。整除的性质：6.设a，b ，c是三个整数，c0 。若c|a， c|b，则 c|(ab) 。7.设a，b ，c是三个整数，c0 。若c|a， c|b，则 对任意整数s和t，有c|(satb) 。8. 设a，b ，c是三个整数， c0 ， c|a， c|b。如果存在整数 s 和 t 使得 satb1，则 c1。整除的性质：9.设a1，a2 ，an，c都是整数，c0 。 若c| a1 ， c| a2 ， c| an ，则对任意整数s1， s2 ，sn， c|(s1a1+

18、 s2a2+ snan) 。10.设a，b 是整数，a0 ，b0 。若a|b， b|a， 则 ab 。课堂练习证明：7.设a，b ，c是三个整数，c0 。若c|a， c|b，则 对任意整数s和t，有c|(satb) 。5. 设a，b ，c是三个整数， b0 ， c0 。若c|b， b|a，则 c|a ，即，整除具有传递性。定义2 设整数n 0 ，1。如果除了显然因数1和n外，n 没有其它因数，那么，n叫素数(或质数或不可约数)，否则n叫合数。若整数n 0 ，n为素数或合数时，-n也为素数或合数。一般素数总是指正整数。通常用p表示。素数：设p是奇素数，如果(p1)/2也是素数，则素数p叫安全素数

19、。如p5， p7， p11， p23，p47，安全素数在RSA密码系统中有应用。定理6. 设n 为正合数，p是n的一个大于1的最小正因数，则 p 一定是素数，且 。证明 反证法。如果p不是素数，则存在整数q (1 q p)使得q | p，但p | n，根据定理一，有q | n。这与p是n的最小正因数矛盾。所以，p 是素数。 因为n 是正合数，所以存在整数n1使得 n pn1 ，1 p n1 n 因此， p 2 pi，i1, 2, , k，所以n一定是合数。根据定理6，n的大于1的最小正因数p是素数。因此，p是p1, p2, , pk中的某一个，即存在j, 1 j k，使得ppj。根据定理3，有

20、p|(n- p1 p2 pk), 即p|1。得到矛盾。故存在有无穷多个素数。欧几里得(Euclid)除法最小非负余数：定理9(欧几里得除法). 设a, b 是两个整数，其中b0。则存在唯一一对整数q, r 使得 a bq + r，0 r b。定义3. 称上式中的q为a被 b 除所得的不完全商，称r 为a被 b 除所得的余数(最小非负余数)。a bq + r，0 r 0。则存在唯一一对整数q, r 使得 a bq + r，0 r 0。则存在唯一一对整数q, r 使得 a bq + r，0 r b。, -3b,-2b,-b, 0, b, 2b, 3b, qb (q+1)ba设a 落在区间qb， (

21、q+1)b)中。因此，存在一个整数q使得 qb a (q+1)b， 即 0 a-bq b。令 ra-bq，则有 a bq + r，0 r 0。则存在唯一一对整数q, r 使得 a bq + r，0 r b。 (1)证明.唯一性. 假设还有一对整数q1, r1 也满足： a bq1 + r1，0 r1 0，整数q, r 使得 a bq + r，0 r b。则 b|a的充要条件是a被b除所得的余数r0。定义4. 设x是实数，称x的整数部分为小于或等于x的最大整数，记成x，这时有x x 0。则对任意整数c，存在唯一一对整数q, r 使得 a bq + r，c r bc。 (4)例如：设a 15， b

22、 6，a bq + r，c r 0。则对任意整数c，存在唯一一对整数q, r 使得 a bq + r，c r bc。证明.存在性. 考虑整数序列： , -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, 序列的各项把实数轴划分成长度为b的区间，, -3b+c, -2b+c, -b+c, c, b+c, 2b+c, 3b+c, a一定落在其中的一个区间中。设a 落在区间qb+c， (q+1)b+c)中。因此，存在一个整数q使得 qb+c a (q+1)b+c， 即 c a-bq b+c

23、。令 ra-bq，则有 a bq + r，c r 0。则对任意整数c，存在唯一一对整数q, r 使得 a bq + r，c r bc。 (4) 假设还有一对整数q1, r1 也满足： a bq1 + r1，c r1 0。则对任意整数c，存在唯一一对整数q, r 使得 a bq + r，c r bc。 (4)例如：设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例如：设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欧几里得除法一般余数1. 当c0 时，0 r b，这时称r为最小非负余数。2. 当c1时，1 r b，这时称r为最小正余数。3. 当cb+1时，b+1 r 0，这时称r为最大非正余数。4. 当cb时，b r 0。则对任意整数c，存在唯一一对整数q, r 使得 a bq + r，c r bc。 (4)5. (i) 当 b2k, ck时, 有 b/2 k r k b/2， (ii) 当 b2k, ck+1时, 有 -b/2 k r k b/2， (iii) 当 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。则对任意整数c，存在唯一一对整数q, r 使得 a bq + r，c r 0，如果b|a，则(a, b )b。 5. 设a1, a2, , an 是 n个不全为零的整数，则 (i) a1, a2, , an与|a1|, |a2|, , |an|的公因数相同。 (ii) (a1, a2, , an)(|a1|, |a2|, , |an| )。6. 设a, b 是两个整数，则 (a, b )(a, b )(a, b ) (| a |, | b |) 。4.设p是一个素数， a是整数，如果p | a，则p与

26、a互素。最大公因数的性质：7. 设 b 是任一正整数，则(0, b )b。8.定理1.3.3 设a, b, c是三个不全为零的整数。如果 a bq + c, 其中q是整数，则有(a, b) (b, c)。9.定理1.3.4 设a, b 是任意两个正整数，则(a, b )rn，其中rn是广义欧几里得除法中最后一个非零余数，有 (a, b)(r1, r2)(r2, r3)(rn-1, rn) (rn, 0) rn10. 定理1.3.5 设a, b是任意两个正整数，则存在整数s和t使得：sa+tb (a, b) 。Bzout(贝祖)等式。最大公因数的性质：11定理1.3.7 设a, b是任意两个正整

27、数,则 对于 j 0, 1, 2, n，sj 和 tj 归纳地定义为 其中 rj ， qj 分别是广义欧几里得除法中的余数和不完全商。j 0, 1, 2, n最大公因数的性质：最大公因数的性质：12.定理1.3.8 整数a, b互素的充分必要条件是存在整数s, t使得 sa + tb 1 13. 设四个整数a, b, c, d 满足关系式：ad bc1 则(a, b)1, (a, c)1, (d, b)1, (d, c)1。最大公因数的性质：14.定理1.3.9 设a, b是任意两个不全为零的整数,d 是正整数,则 d 是整数a, b的最大公因数的充要条件是： (i) d|a, d|b； (i

28、i) 若e|a, e|b, 则 e|d。 最大公因数的性质：15.定理1.3.10 设a, b是任意两个不全为零的整数, (i) 若 m 是任一正整数,则(ma, mb)m (a, b). (ii) 若非零整数 d 满足d|a, d|b, 则特别的：最大公因数的性质：17.定理1.3.12 设 a1, a2, , an，c为正整数, 如果 (ai , c) 1, 1in,则 (a1 a2 an，c) 1.16.定理1.3.11 设a, b, c是三个整数, 且b0, c0, 如果 (a, c)1, 则(ab, c) (b, c)最大公因数的性质：18.定理1.3.13 设a, b和u, v都是

29、不全为零的整数,如果a qu + rv， b su + tv，其中q , r，s , t是整数,且qt - rs 1，则 (a, b ) (u, v ) 。最大公因数在可逆变换下的不变性。最大公因数的性质： 19.引理1.3.2 设a,b是两个正整数,则 和 的最大公因数是 。 20.定理1.3.16 设a,b是两个正整数,则正整数 和 互素的充要条件是 a 和 b 互素.最大公因数的性质：21.定理1.4.1 设 a, b，c是三个整数,且c0。如果 c|ab，(a , c) 1, 则 c|b.22.定理1.4.2 设p 是素数,若 p|ab,则 p|a或p|b 。23.定理1.4.3 设

30、a1, a2, , an 是 n 个整数,p 是素数,若 p|a1 a2an,则 p 一定整除某一个ak, 1kn。最大公因数的性质证明：2.设a, b 是两个整数，则(a, b )(b, a )。3.设a, b 是两个整数，b 0，如果b|a，则(a, b )b。最大公因数的性质证明：4.设p是一个素数， a是整数，如果p | a，则p与a互素。证明. 设(p, a )d，则有d | p， d | a。 因为p是素数，所以由d | p， 有d1或dp。 若dp，由d | a ，有p | a，这与假设p | a矛盾。因此，d1，即(p, a )1，结论成立。最大公因数的性质证明： 5. 设a1

31、, a2, , an 是 n个不全为零的整数，则 (i) a1, a2, , an与|a1|, |a2|, , |an|的公因数相同。 (ii) (a1, a2, , an)(|a1|, |a2|, , |an| )。6. 设a, b 是两个整数，则 (a, b )(a, b )(a, b ) (| a |, | b |) 。7. 设 b 是任一正整数，则(0, b )b。8.定理1.3.3 设a, b, c是三个不全为零的整数。如果 a bq + c, 其中q是整数，则有(a, b) (b, c)。最大公因数的性质：证明. 设d(a, b )，d(b, c )，则d|a, d|b。所以 d

32、| (a(q)b), 即d|c。因而d是b，c的公因数。从而d d。又d |b, d |c，可得d | (bq c), 即d | a 。因而d是a，b的公因数。从而d d。 所以dd，即(a, b) (b, c)。例10：设a1859，b1573，求(a, b) 因为185911573286，所以 (1859, 1573) (1573, 286) 又所以 (1573, 286) (286, 143) 28621430 ，所以 (286, 143) (143, 0) 143所以 (1859, 1573) 143利用定理3 可计算两个整数a, b的最大公因数。课堂练习：设

33、a1071，b462，求(a, b)解 10712462147 462314721 147721 所以 (1071, 642) 21令r0 a，r1 b， 反复运用欧几里得除法(称为广义欧几里得除法)可得：最大公因数的求法：广义欧几里得除法设a, b 是任意两个正整数，求a, b 的最大公因数 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 根据定理1.3.3有

34、 (a, b)(r1, r2)(r2, r3)(rn-1, rn) (rn, 0) rn9.定理1.3.4 设a, b 是任意两个正整数，则(a, b )rn，其中rn是广义欧几里得除法中最后一个非零余数，有 (a, b)(r1, r2)(r2, r3)(rn-1, rn) (rn, 0) rn (a, b) (r1, r2) (r2, r3) (rn-1, rn) (rn, 0) rn例：设a169，b121，求 (a, b) 用广义欧几里德除法求两个整数的最大公因数， 可以用：（1）最小非负余数：（2）绝对值最小余数：（3）最小非正余数：求两个整数的最大公因数的过程：（1）将求两个整数的最

35、大公因数转化为求两个非负整数的最大公因数；（2）运用广义欧几里得除法，根据定理1.3.3 ，将求两个正整数的最大公因数转化为求两个较小非负整数的最大公因数(用较小的数除较大的数，可考虑不同余数)；（3）运用广义欧几里得除法，将求两个正整数的最大公因数转化为求0和一个正整数的最大公因数；例12：设a1859，b1573，求(a, b) 解 由定理1 (1859, 1573) (1859, 1573) 运用广义欧几里得除法，有 1859115732862862143 根据定理4 (1859, 1573) 143课堂练习：设a24871，b3468，求(a, b)解 运用广

36、义欧几里得除法，有 2487173468595 34685595493 5951493 102 493410285 10218517 85517 所以 (24871, 3468) 17课堂练习：设a24871，b3468，求(a, b)解 运用广义欧几里得除法，有 2487173468595 34686595 102 5956102 17 102617 所以 (24871, 3468) 1710. 定理1.3.5 设a, b是任意两个正整数，则存在整数s和t使得：sa+tb (a, b) 。Bzout(贝祖)等式。 最大公因数的性质证明：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。课堂练习：设a24871，b3468，求(a, b)课堂练习：a24871，b3468，求 s 和 t 使得 sa+tb (a, b) 。课堂练习：设a24871，b3468，求(a, b)解 运用广义欧几里得除法，有

39、2487173468595 34685595493 5951493 102 493410285 10218517 85517 所以 (24871, 3468) 17课堂练习：设a24871，b3468，求(a, b)解 运用广义欧几里得除法，有 2487173468595 34686595 102 5956102 17 102617 所以 (24871, 3468) 17课堂练习：a24871，b3468，求 s 和 t 使得 sa+tb (a, b) 。解 运用广义欧几里得除法，有 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课堂练习：a24871，b3468，求 s 和 t 使得 sa+tb (a, b) 。17 610259517 6(65953468) 595 35595 634681735(24871 73468)63468 3524871 251493s35, t 251解 运用广义欧几里

41、得除法，有 248717346859534686595 1025956102 17102617(24871, 3468) 1711定理1.3.7 设a, b是任意两个正整数,则 对于 j 0, 1, 2, n，sj 和 tj 归纳地定义为 其中 rj ， qj 分别是广义欧几里得除法中的余数和不完全商。j 0, 1, 2, n最大公因数的性质：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 最大公因数的性质证

42、明：12.定理1.3.8 整数a, b互素的充分必要条件是存在整数s, t 使得 sa + tb 1 。13. 设四个整数a, b, c, d 满足关系式：ad bc1 则(a, b)1, (a, c)1, (d, b)1, (d, c)1。作业：p49：24， 25， 28(3)，29(1,2)，32(4)，最大公因数的性质证明：14.定理1.3.9 设a, b是任意两个不全为零的整数,d 是正整数,则 d 是整数a, b的最大公因数的充要条件是： (i) d|a, d|b； (ii) 若e|a, e|b, 则 e|d。 证明：若d 是整数a, b的最大公因数，则(i) 成立。由定理1.3.

43、7，存在整数s和t使得 sa+tb (a, b) d 。因此当e|a, e|b 时， 有 e| sa+tb d。即(ii) 成立。最大公因数的性质证明：14.定理1.3.9 设a, b是任意两个不全为零的整数,d 是正整数,则 d 是整数a, b的最大公因数的充要条件是： (i) d|a, d|b； (ii) 若e|a, e|b, 则 e|d。 证明：反之，设(i), (ii)成立，那么， (i) 说明 d是整数a, b的公因数。(ii)因为e|d时，有|e|d。说明d是整数a, b的公因数中的最大数。因此，d 是整数a, b的最大公因数 最大公因数的性质证明：15.定理1.3.10设a, b

44、是任意两个不全为零的整数, (i) 若 m 是任一正整数,则(am, bm)(a, b)m. (ii) 若非零整数 d 满足d|a, d|b, 则特别的：证 令 d(ab,c), d(b,c)。我们有 d|b, d|c, 进而 d|ab, d|c。根据定理1.3.9, 我们得到 d|d.反过来,因为(a,c)1,根据定理1.3.8,存在整数 s,t 使得 sa + tc 1两端同乘 b, 得到s(ab) + (tb)c b根据定理1.1.3,由d|ab,d|c,我们得到d|s(ab)+(tb)c,即d|b。同样,根据定理1.3.9,我们得到d|d 。故 d d。 最大公因数的性质证明： 16.

45、定理1.3.11 设a, b, c是三个整数, 且 b0, c0, 如果 (a, c)1, 则(ab, c) (b, c)最大公因数的性质证明：17.定理1.3.12 设 a1, a2, , an，c为正整数, 如果 (ai , c) 1, 1in,则 (a1 a2 an，c) 1.证明：对n作数学归纳法。n2 时, 就是定理1.3.11 假设n1 时,命题成立。即 (a1 a2 an1，c) 1 对于n, 根据归纳假设 (a1 a2 an1 , c) 1, 再根据(an , c) 1, 及定理1, 得到既命题对所有的n成立。最大公因数的性质证明：18.定理1.3.13 设a, b和u, v都

46、是不全为零的整数,如果a qu + rv， b su + tv，其中q , r，s , t是整数,且qt - rs 1，则 (a, b ) (u, v ) 。最大公因数在可逆变换下的不变性。证 令 d(a, b), d(u,v)，则 d|u, d|v, 由定理1.1.3得 d| qu + rv a, d| su + tv b。因而d|d.又由假设可得uta + (-r)b， v(-s)a + qb同理可得得到d|d 。故 d d。 最大公因数的性质证明： 19.引理1.3.2 设a,b是两个正整数,则 和 的最大公因数是 。 20.定理1.3.16 设a,b是两个正整数,则正整数 和 互素的充

47、要条件是 a 和 b 互素.引理1 设a, b是两个正整数.若a bq + r, 其中 r 是 a 被 b 除的最小正余数(1 r b) 。则 2a1 被2b1除的最小正余数是2r1 (1 2r1 2b1) 。证 当a 0是a1, a2, , an的最大公因数当且仅当： (1) d|a1, d|a2, , d| an, (最大公因数是每个数的因数) (2) 若e|a1, e|a2, , e| an ，则e|d 。(每个公因数都整除最大公因数)大整数运算大整数存储由于大整数的位数太多，我们首先要做的是把它“拆”开来，存放在若干个地方，然后建立不同存储地址之间的联系。对于大整数1112223334

48、445用一维数组存储:001112223334445用链表存储：45head 44332322111用数组存储大整数(12345678901234567890)123456789012345678901234567890123456789012345678901234567890用数组存储大整数时，每一个数组元素表示多位整数,时空效率要比每一个数组元素表示一位整数好。每个数组元素表示5位整数时最好；取6位时，相乘可能溢出。大整数的加法运算+468818814582811000714890203010910070148901913001123456789012345678900097661470

49、00079625679800大整数的乘法运算3456789525679823160489653710338765864197375+88769663002109895=93109878+93=77379856+77=55659834+55=33876795=63656778+63=52896756+52=38046734+38=23162595=23752578+23=19732534+14=8642556+19=1419作业：p50：35， 36， 37，课外练习：1. 用广义欧几里得除法求两个整数的最大公因数。2. 用定理1.3.7求s和t使得：sa+tb (a, b) 。 要求对任意整数

50、给出结果。定义 1 设 a1, a2, , an是 n 个整数，若 D 是这 n个数的倍数，则 D 叫做这 n 个数的一个公倍数。 a1, a2, , an 的所有公倍数中的最小正整数叫做最小公倍数。记作 a1, a2, , an。若 D 是a1, a2, , an最的小公倍数，则 D a1, a2, , an。1.4.2 最小公倍数例 14和21的公倍数为 42, 84, ， 14和21的最小正公倍数为 42 。最小公倍数的性质：1 设 a1, a2, , an是 n 个整数，则整数 D 是a1, a2, , an最的小公倍数，即 D a1, a2, , an当且仅当 （i） ai | D,

51、 1in; (最小公倍数是每个数的倍数) (ii) 若 ai | D, 1 in, 则 D | D。 (每个公倍数都能被最小公倍数整除)最小公倍数的性质：2. a, b的最小公倍数 D a, b 是集合c | cZ, a|c, b|c 中的最小正整数。类似的： a1, a2, , an的最小公倍数 D a1, a2, , an 是集合 c | cZ, ai|c, 1in中的最小正整数。最小公倍数的性质：3. 定理 1.4.4 设 a, b 是两个互素的正整数(a , b)1,则 (i) 若a | D, b | D, 则 a b | D; (ii) a, b a b.4. 设p，q是两个不同的素

52、数，则p, q p q。5. (50页第39题)设a, b是任意两个不全为零的整数若m是任一正整数，则m a, m bm a, b 。最小公倍数的性质：6. 定理 1.4.5 设a, b 是两个正整数，则 (i)若 a|D, b|D, 则a, b|D (ii) 即 a, b (a, b) a b 7. 定理1.4.6 设a1, a2, , an是n个整数。令 则最小公倍数的性质：8. 定理1.4.7 设a1, a2, , an是n个正整数。如果 则最小公倍数的性质证明：3. 定理 1.4.4设 a, b 是两个互素的正整数(a , b)1,则 (i) 若a| D, b| D, 则 a b |

53、D; (ii) a, b a b. 证明： 设 a| D ，则D a k。又b| D, 即 b| a k, 由(a, b)1, 根据定理1.3.11的推论，得到b|k。 因此 k bt, 进而D abt。故a b| D 。(i)得证。 即 a b 是a, b 的公倍数。又由 (i) 知，对a b的任一公倍数D ，都有a b D 。所以a b是a, b 的公倍数中最小正整数, 故a, ba b。5. (50页第39题)设a, b是任意两个不全为零的整数若m是任一正整数，则am, bma, bm。. 最小公倍数的性质证明：证明:设 L a, b，则 a L， b L，进而am Lm， bm Lm，

54、即Lm是am, bm的公倍数。所以am, bm Lm a, bm。反之，设L am, bm，及L k1am ， L k2bm ，由此知，5. (50页第39题)设a, b是任意两个不全为零的整数若m是任一正整数，则am, bma, bm。最小公倍数的性质：5. (50页第39题)设a, b是任意两个不全为零的整数若m是任一正整数，则am, bma, bm。. 最小公倍数的性质： 最大公因数的性质：15.定理1.3.10 设a, b是任意两个不全为零的整数, (i) 若 m 是任一正整数,则(am, bm)(a, b)m. (ii) 若非零整数 d 满足d|a, d|b, 则最小公倍数的性质证明

55、：6. 定理 1.4.5 设a, b 是两个正整数，则 (i)若 a|D, b|D, 则a, b|D (ii) 即 a, b (a, b) a b 证明：先证明(ii)成立 令d (a，b), 根据定理1.3.10，有根据定理1.4,4， 。进而，即(ii)成立。(?)证明：证明(i)成立 由得到，从而，即(i)成立。根据 (?)定理1.4.4例 计算最小公倍数 1400，2100。 解 因为 (1400, 2100) 700 所以最小公倍数的性质证明：例 5 计算最小公倍数12，15，21，35。 解 因为 12, 15 60 60, 21 420 420, 35 420所以最小公倍数12，

56、15，21，35420.最小公倍数的性质证明：8. 定理1.4.7 设a1, a2, , an是n个正整数。如果 则1.5 整数分解定理 1.5.1 (整数分解定理)给定正合数 n 1。如果存在整数a，b使得 n | a2b2 ，n | ab ，n | ab ，则(n，ab)和(n，ab)都是n的真因数(除1和本身以外的因数)。定理 1.5.1 (整数分解定理)给定正合数 n 1。如果存在整数a，b使得 n | a2b2 ，n | ab ，n | ab ，则(n，ab)和(n，ab)都是n的真因数。证 若(n，ab)不是n的真因数，则(n，ab)为1或n 。若(n，ab) 1，由n | a2b

57、2 知n | (ab) (a b)，得n | (a b)，与假设矛盾。若(n，ab) n ，推出n | (ab) ，与假设矛盾。故(n，ab)是n的真因数。同理，(n，ab) 是n的真因数。1.6 算术基本定理定理 1.6.1 (算术基本定理)任一整数 n 1都可以表示成素数的乘积，且在不考虑乘积顺序的情况下，该表达式是唯一的。 即 n p1 p2 ps , p1 p2 ps (1)其中 pi 是素数，并且若 n q1 q2 qt , q1 q2 qt其中 qi 是素数，则 t s, qi pi ，1 i t.证 对 n 用数学归纳法证明： n p1 p2 ps , p1 p2 ps (1)

58、当n2时，(1)式成立。 假设对于小于n的正整数，(1)式成立。 对于正整数 n， 若 n 是素数，则(1)式对 n 成立。 若 n 是合数，则存在正整数 n1, n2 使得 n n1 n2, 1 n1 n, 1 n2 1 可以唯一地表示成其中 pi pj ( i 1 ，且有标准分解式则 d 是 n 的正因数当且仅当 d 有因数分解式：例 写出整数21，100的所有正因数。解 213 7 ， 21 的所有正因数为：30 70 ， 31 70 ， 30 71 ， 31 71 1, 3, 7, 21例 写出整数21，100的所有正因数。解 100 22 52 ， 100 的所有正因数为：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 设正整数 n 有因数分解式则 n 的正因数个数证明：设 d 是正整数 n 的正因数，根据定理3，因为 1 的变化范围是从 0 到 1 ，共有1 1个值，因为 2 的变化范围是从 0 到 2 ，共有1 2个值，因为 s 的变化范围是从 0 到 s ，共有1 s个值， 所以 n 的因数个数为定理 1.6.4 设a，b是两个正整数，且有素因数分解则 a 和 b 的最大公因数和最小公倍数有因数分解：证明

60、： 根据定理1.6.3，整数满足最大公因数的定义，所以同理，整数满足最小公倍数的定义，所以例：计算120，150，210，35的最大公因数和 最小公倍数 。解：12023 3 5 ， 150 2 3 52 2102 3 5 7 ， 35 5 7根据定理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同样，根据定理1.6.4 ， 120, 15023 3 52 600， 600, 210 23 3 5