第1章-整数的可除性课件.pptx_163文库

资源描述

1、信息安全数学基础周杰周杰课程简介课程简介教学方式：理论课教学教学方式：理论课教学总学时：总学时：48 考核方式：考试考核方式：考试(70%)+(作业作业+平时平时)(30%)课课程学分：程学分：3 先修课程：无先修课程：无教材、参考书：陈恭亮教材、参考书：陈恭亮信息安全数学基础信息安全数学基础简明信息安全数学基础简明信息安全数学基础潘承洞潘承洞,潘承彪潘承彪初等数论初等数论后续课程：密码学与安全协议后续课程：密码学与安全协议密码学简介密码学简介密码学密码学 Cryptology 维基百科：研究如何隐密地传递信息的学科维基百科：研究如何隐密地传递信息的学科是指对信息以及其传

2、输的数学性质的研究，是数是指对信息以及其传输的数学性质的研究，是数学和计算机科学的分支，和信息论密切相关学和计算机科学的分支，和信息论密切相关。Wo ent out nh u ote ll orm dic e kodw?yemiiWould you like to come to dinner with me?密码学简介密码学简介密码学密码学 Cryptology 百度百科：研究编制密码和破译密码技术的科学百度百科：研究编制密码和破译密码技术的科学研究密码变化的客观规律，应用于编制密码以保研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为守通信秘密的，称为编码学编码学；应用于破译

3、密码以；应用于破译密码以获取通信情报的，称获取通信情报的，称为为解码解码学学，总称，总称密码学密码学密码学简介密码学简介密码学密码学 Cryptology 密密码学是信息安码学是信息安全中的相全中的相关议题，如关议题，如认证认证、访问访问控制控制的核心。密码学的首要目的是的核心。密码学的首要目的是隐藏信息的涵义隐藏信息的涵义，并不是隐藏信息的存在。并不是隐藏信息的存在。密码学已被应用在日常生活：包括自动柜员机的密码学已被应用在日常生活：包括自动柜员机的芯片卡、电脑使用者存取密码、电子商务等等。芯片卡、电脑使用者存取密码、电子商务等等。密码学简介密码学简介明文明文(plaintext)任何人

4、都任何人都读读得得懂懂的文字的文字密文密文(encrypted;cipher text)用特殊方法使用特殊方法使明文内明文内容容变得混乱变得混乱，使得只有持，使得只有持有有“密钥密钥”的人才能的人才能恢复出明文。恢复出明文。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 解密解密(decry

5、pt)Would you like to come to dinner with me?保密系统模型保密系统模型保密系统模保密系统模型型图图搭线信道搭线信道搭线信道搭线信道非非法法(主动攻击主动攻击)(被动攻击被动攻击)密码分析员密码分析员 m 接入者接入者 c (窃听者窃听者)信信源源m 加密器加密器 c 解密器解密器m 接收者接收者mc=Ek1(m)信道信道m=D k2(c)k1 k2 密钥源密钥源密钥源密钥源 k1 密钥信道密钥信道 k2 m明文明文密文密文监听、截取、更改、增加监听、截取、更改、增加加密密钥加密密钥解密密钥解密密钥加密方法加密方法解密方法解密方法明文明文机

6、机密性密性防止防止窃听窃听完整性完整性内容内容不可被更改不可被更改鉴定性鉴定性确确定定信息确实信息确实是由是由真正的发送者所传送真正的发送者所传送不可不可否认性否认性发送发送方在方在事后事后不可否不可否认其传送的消息认其传送的消息密码学主要目标密码学主要目标密码学历史密码学历史密码学密码学的的历史历史已有四千多年已有四千多年早期的密码学主要作为军事用途。早期的密码学主要作为军事用途。Caesar Cipher(凯撒密码凯撒密码)(2千年前千年前罗马罗马)每每个个字母用其字母用其前前(后后)面的面的字母替代字母替代 A Z;B A;一般形式，一般形式，Caesar Ciph

7、er 中字母移动的位数可以为中字母移动的位数可以为1-25中的任何一个中的任何一个DECHEXCHARACTER(CODE)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

8、)55END OF QUERY(ENQ)2115NEGATIVE ACKNOWLEDGEMENT(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

9、 SEPARATOR(FS)RIGHT ARROW13 DCR(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 x42B

10、980 x62b350 x23#670 x43C990 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 x6Cl45 0 x2D-770 x4DM1090 x6Dm460 x2E.780 x4EN11

11、00 x6En470 x2F/790 x4FO1110 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 x

12、78x570 x399890 x59Y1210 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码码727374757

13、67778字母字母OPQRSTUASCII码码79808182838485字母字母VWXYZASCII码码8687888990明文明文P：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

14、 WILL BEGIN71 79 71 83 86 86 76 79 81 83 88xy10解密方法解密方法密钥为密钥为1061 69 61 73 76 76 66 69 71 73 78xx26 当当 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世纪世纪)第一次世界大战第一次世界大战无线电的发明，无线电的发明，电码本电码本。第二次世界大战第二次世界大战以机械代替人手的加密方法。以

15、机械代替人手的加密方法。密码学历史密码学历史德国的洛伦兹密码机，德国的洛伦兹密码机，加密机密邮件加密机密邮件上世纪上世纪70年代中期年代中期,首次出现了现代分组密码首次出现了现代分组密码DES 1976年，年，Diffie和和Hellman 在在“密码学新方向密码学新方向”一一文中首次提出文中首次提出公钥密码公钥密码的思想的思想使用两个密钥：公钥、私钥使用两个密钥：公钥、私钥加密和解密不是对称的加密和解密不是对称的是对对称密码的重要补充是对对称密码的重要补充 DiffieHellman密钥交换方法密钥交换方法Diffie W,Hellman M E.New directions in

16、 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.,Adle

17、man,L.A.:A method for obtaining 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算法算法是当前

18、在互联网传输、银行以及信用卡产是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制。业中被广泛使用的安全基本机制。Rivest,R.L.,Shamir,A.,Adleman,L.A Shamir2008年年4月月24日下午日下午世界著名密码学家、世界著名密码学家、图灵奖获得者以色列图灵奖获得者以色列Weizmann科学院教授科学院教授 Adi Shamir教授做客清教授做客清华论坛华论坛2010年年5月山东大学授月山东大学授予予Adi Shamir教授名誉教授名誉博士学位博士学位第一章整数的可除性 1.1 整除的概念整除的概念欧几里德除法欧几里德除法定义定义1 设设a，b

19、是任意两个整数，是任意两个整数，b0。若有整数。若有整数q使使 abq，就称就称b整除整除a，或，或a被被b整除，记作整除，记作b|a，并把，并把b叫叫a的因数，的因数，a叫叫b的倍数。的倍数。q也整除也整除a，或，或a被被q整除，即有整除，即有q|a，并且，并且q是是a的因数，的因数，a也是也是q的倍数。记做的倍数。记做babaq/整数：整数：Z,-2,-1,0,1,2,定义定义1 如果使得如果使得abq的的整数整数q不存在，称不存在，称b不整除不整除a，或或a不能被不能被b整除。记作整除。记作b|a。整除的性质：整除的性质：1.如果如果b整除整除a，即即abq。则。则(1)当当b遍历整数遍

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

21、，b 0。若。若b|a，则，则 b|(-a),(-b)|a,(-b)|(-a),b|a|,|b|a,|b|a|。5.设设a，b，c是三个整数，是三个整数，b 0，c 0。若。若c|b，b|a，则，则 c|a，即，整，即，整除具有传递性。除具有传递性。整除的性质：整除的性质：6.设设a，b，c是三个整数，是三个整数，c 0。若。若c|a，c|b，则，则 c|(a b)。7.设设a，b，c是三个整数，是三个整数，c 0。若。若c|a，c|b，则，则对对任意任意整数整数s和和t，有，有c|(sa tb)。8.设设a，b，c是三个整数，是三个整数，c 0，c|a，c|b。如果。如果存在存在整数整数

22、s 和和 t 使得使得 sa tb1，则，则 c 1。整除的性质：整除的性质：9.设设a1，a2，an，c都是整数，都是整数，c 0。若若c|a1，c|a2，c|an，则对，则对任意任意整数整数s1，s2，sn，c|(s1a1+s2a2+snan)。10.设设a，b 是整数，是整数，a 0，b 0。若。若a|b，b|a，则则 a b。课堂练习课堂练习证明：证明：7.设设a，b，c是三个整数，是三个整数，c 0。若。若c|a，c|b，则，则对对任任意意整数整数s和和t，有，有c|(sa tb)。5.设设a，b，c是三个整数，是三个整数，b 0，c 0。若。若c|b，b|a，则，则 c|a，即，

23、整，即，整除具有传递性。除具有传递性。定义定义2 设整数设整数n 0，1。如果除了显然因数。如果除了显然因数 1和和 n外，外，n 没有其它因数，那么，没有其它因数，那么，n叫叫素数素数(或或质数质数或或不不可约数可约数)，否则，否则n叫叫合数合数。若整数若整数n 0，n为素数或合数时，为素数或合数时，-n也为素数或合数。也为素数或合数。一般素数总是指正整数。通常用一般素数总是指正整数。通常用p表示。表示。素数：素数：设设p是奇素数，如果是奇素数，如果(p1)/2也是素数，则素数也是素数，则素数p叫叫安全安全素数素数。如如p5，p7，p11，p23，p47，安全素数在安全素数在RSA密码系统中

24、有应用。密码系统中有应用。定理定理6.设设n 为正合数，为正合数，p是是n的一个大于的一个大于1的最小正因数，的最小正因数，则则 p 一定是素数，且一定是素数，且。pn证明证明反证法。如果反证法。如果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一定是合数。根据定一定是合数。根

25、据定理理6，n的大于的大于1的最小正因数的最小正因数p是素数。因此，是素数。因此，p是是p1,p2,pk中的某一个，即存在中的某一个，即存在j,1 j k，使得，使得ppj。根据定理根据定理3，有，有p|(n-p1 p2 pk),即即p|1。得到矛盾。故存在有无穷多个素数。得到矛盾。故存在有无穷多个素数。欧几里得欧几里得(Euclid)除除法法最小非负余数：最小非负余数：定理定理9(欧几里得除法欧几里得除法).设设a,b 是两个整数，其中是两个整数，其中b0。则存在则存在唯一一对唯一一对整数整数q,r 使得使得 a bq+r，0 r b。定义定义3.称上式中的称上式中的q为为a被被 b 除所得

26、的除所得的不完全商不完全商，称，称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，(q+1)b)中。中。因因此，存在一个整数此，存在一个整数q使得使得 qb a(q+1)b，即即 0 a-bq b。令令 ra-bq，则有，则有 a bq+r，0 r 0。则存在唯一一对整数则存在唯一一对整数q,r

27、使得使得 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 6，a bq+r，

28、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)中中。因因此，存在一个整数此，存在一个整数

29、q使得使得 qb+c a(q+1)b+c，即即 c a-bq b+c。令令 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 ，

30、323212871999例如：设例如：设a 230，b 7，a bq+r，c r bc。取取 c 0：r ，q ，c 1：r ，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

31、 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)/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|,|a

32、n|的的公因数公因数相同。相同。(ii)(a1,a2,an)(|a1|,|a2|,|an|)。6.设设a,b 是两个整数，则是两个整数，则 (a,b)(a,b)(a,b)(|a|,|b|)。4.设设p是一个素数，是一个素数，a是整数，如果是整数，如果p|a，则，则p与与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 是任意两个正整数，则是

33、任意两个正整数，则(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是任意两个正整数是任意两个正整数,则则对于对于 j 0,1,2,n，sj 和和 tj 归纳地定义为归纳地定义为),(barbtasnnn,1,0,0,1112

34、1211212jjjjjjjjtqttttsqssss其中其中 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是任意两个不全

35、为零的整数是任意两个不全为零的整数,d 是正是正整数整数,则则 d 是整数是整数a,b的最大公因数的充要条件是：的最大公因数的充要条件是：(i)d|a,d|b；(ii)若若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,则则|),(,dbadbda 特别的：特别的：1),(,),(babbaa最大公因数的性质最大公因数的性质：17.定理定理1.3.12 设设

36、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都都是不是不全为零的整数全为零的整数,如果如果a qu+rv，b su+tv，其其中中q,r，s,t是是整整数数,且且qt-rs 1，则则 (a,b)(u,v)。最最大公因数在大公因数在可逆变换下的不变性可逆变换下的不变性。最大公因数的性质：最大公因数的性质：19.引理引理1.3.2

37、设设a,b是两个正整数是两个正整数,则则和和的最大公因数是的最大公因数是。20.定理定理1.3.16 设设a,b是两个正整数是两个正整数,则正整数则正整数和和互素的充要条件是互素的充要条件是 a 和和 b 互素互素.12 a12 b12),(ba12 a12 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 设设 a1,a2,an 是是 n 个整数个整数,p 是

39、|a矛盾。矛盾。因此，因此，d1，即，即(p,a)1，结论成立。，结论成立。最大公因数的性最大公因数的性质证明：质证明：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|)。7.设设 b 是任一是任一正整数正整数，则，则(0,b)b。8.定理定理1.3.3 设设a,b,c是三个不全为零的整数。如果是三个不全为零的整数。如果 a bq+c

41、所以 (1573,286)(286,143)28621430，所以，所以 (286,143)(143,0)143所以所以 (1859,1573)143利用利用定理定理3 可计算两个整数可计算两个整数a,b的最大公因数。的最大公因数。课课堂练习：堂练习：设设a1071，b462，求，求(a,b)解解 10712462147 462314721 147721 所以所以 (1071,642)21令令r0 a，r1 b，反复运用欧几里得除反复运用欧几里得除法法(称为称为广广义欧几里得除法义欧几里得除法)可可得：得：最大公因数的求法最大公因数的求法：广义欧几里得除法广义欧几里得除法设设a,b 是任意两个

42、正整数，求是任意两个正整数，求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有有 (a,b)(r1,r2)(r2,r3)(rn-1,rn)(rn,0)rn9.定理定理1.3.4 设设a,b 是任意两个正整数，则是任意两个正整数，则(a,b)rn，其中其中rn是广义欧几里得除法中最后一个非零余数

43、是广义欧几里得除法中最后一个非零余数，有，有 (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）将求）将求两个整数两个整数的最大公因数转化为求两个的最大公因数转化为求两个非负非负

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

45、1573)运用广义欧几里得除法，有运用广义欧几里得除法，有 185911573286 15735286143 2862143 根据定理根据定理4 (1859,1573)143课堂练习：课堂练习：设设a24871，b3468，求，求(a,b)解解运用广义欧几里得除法，有运用广义欧几里得除法，有 2487173468595 34685595493 5951493 102 493410285 10218517 85517 所以所以 (24871,3468)17课堂练习：课堂练习：设设a24871，b3468，求，求(a,b)解解运用广义欧几里得除法，有运用广义欧几里得除法，有 248717346

46、8595 34686595 102 5956102 17 102617 所以所以 (24871,3468)1710.定理定理1.3.5 设设a,b是任意两个正整数，则存在整数是任意两个正整数，则存在整数s和和t使得：使得：sa+tb (a,b)。Bzout(贝祖贝祖)等式等式。112nnnnqrrr2231nnnnqrrr 1102qrrr最大公因数的性最大公因数的性质证明：质证明：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

47、(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 423323 210110 33 解：解：110 33 (102 423)3(23 210)1027 236 10 1027 236(102 423)

48、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)解解运用广义欧几里得除法，有运用广义欧几里得除法，有 2487173468595 34685595493 5951493 102

49、 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 1024934102851021851

50、7 85517(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解解运用广义

展开阅读全文