信息安全数学基础1推荐课件

1、2021/8/221信息安全数学基础张张 立立 江江2021/8/222网络安全(应用技术)密码学(理论基础)信息安全信息安全数学(数论、代数和椭圆曲线理论)身份识别技术、防火墙技术、入侵检测技术等2021/8/223课程内容课程内容数论代数(群、环、域)-新第8章(第8,9,10,11,12章)椭圆曲线-新第9章(第13章)同余式(第3章)二次同余式与平方剩余(第4章)原根与指标(第5章)素性检测(第6+14章)连分数(第7章)不定方程与同余(第2章)整数的可除性(第1章)选用教材：信息安全数学基础陈恭亮 著参考书目： 初等数论 潘承洞 潘承彪 著代数学引论 第2版 聂灵沼 丁石孙 著“Co

2、mmutative Algebra”第1、2卷 O. Zariski & P. Samuel 著“Primality and Cryptography”E. Kranakis 著椭圆曲线密码学导论张焕国 等译2021/8/224课件邮箱 邮箱：邮箱： 密码：密码：1234562021/8/2252021/8/226信息安全数学基础第1章：整数的可除性数的集合：，-3，-2，-1，0，1，2，3， 在数学中有一门称为“整数论”的分支早在公元前50年左右，在我国第一部数学专著九章算术九章算术(作者不详)的第一章中就开始讨论整数，介绍了辗转相除法它与公元前三世纪欧几里德所著几何原本几何原本中

3、介绍的辗转相除法是各自独立地总结出来的五世纪时，在我国的孙子算经孙子算经中更有闻名于世的中国剩余定理(即孙子定理)，也对整数做了研究整数论是研究整数的学科整数什么叫整数？整数的一部分最简单的数学模型就是自然数自然数的严格定义是在集合论的基础上，由Peano(皮亚诺)给出了自然数公理如果有一些对象(可数集)，除了它们的数目之外其它性质我们不予考虑的话，我们就可以用自然数来数它们无穷大总有一些数目由于太大而没有名称。这种现象或许就是人们第一次碰到无穷大这在古代就已经导致这种严肃的问题：有没有大得不能数的数？阿基米德在一本题为数沙器(公元前200年)的书中回答了他列举了一系列增长很快的数目，并且通过

4、体积的估计而证明：这些数目当中有些数目比地球上甚至比太阳系中的沙粒的数目还大素数的数目是有限多还是无穷多？有了研究的对象集合，再建立对象集合上的运算。一些乘法的经验表明，有些数是一些比1大的其它数的乘积而有些数，就没有这种性质-质数(素数)在欧几里德的原本中，已经有一个简单而巧妙的推理能够得出结论：质数无穷质数无穷多多计算机只能处理有限数和有限个数，计算机的计算模型，硬件体系结构的设计与实现，代数编码，软件设计与实现，计算机通信及密码学等，都广泛使用了整数理论而数学数学可以处理无穷大数论特点任意两个整数可以相加，相减，相乘，结果仍是整数但两个整数不一定能在整数的范围内相除，这是整数系统的特点研

5、究整数就针对这一特点加以分析实际上，研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题数论内容介绍数论中一些最基本的事实介绍整数的一些最基本的性质有时似乎在叙述或证明一些尽人皆知非常明显的事实。实则并非如此有些事情，我们习而不察，知其然而不知其所以然。有些事情，虽然知道，却知道的不确切若未特别指明，凡出现的数都是指整数本章主要内容：整除的概念欧几里得算法(*)整数的表示最大公因子与广义欧几里得算法(*)最小公倍数素数与算数基本定理(*)素数定理2021/8/2213141.1 1.1 整除的概念整除的概念 欧几里得除法欧几里得除法一、整除基本概念及性质一、整除基本概念及

6、性质 ,0,| .1a bbqabqbaabb a 设设是是任任意意两两个个整整数数, ,其其中中如如果果存存在在一一个个整整数数 使使得得等等式式成成立立, ,则则称称或或者者 被被 整整除除, ,记记作作整整除除定定义义 如如果果 不不能能整整除除则则记记作作,|.baba 因因数数如如果果则则 叫叫做做 的的而而 叫叫做做 的的倍倍数数| ,.b abaab写写成成或或/.aa bb此此时时 可可q15 当当 遍遍历历整整数数 的的所所有有因因数数时时也也遍遍历历整整数数 的的所所有有因因数数(2), /.baa ba (1),.:baba 当当整整数数 的的所所有有因因数数时时也也遍遍

7、历历整整数数注注遍遍 的的所所有有因因数数历历 对对任任何何整整数数有有(5)0,| .aa a 对对任任何何整整数数有有(3)0,| 0.bb 对对任任何何整整数数有有1|1|(4),.bb 若若则则(6)| ,|(),()|().b ababa2021/8/221617 设设是是三三个个整整数数. .则则定定理理若若1,0,0| ,| ,| .a bcc b b ac a12, | .q qc a因因是是整整数数 所所以以12|c bb aqq证证 设设，则则存存在在整整数数 ， ，使使得得12bcqabq，于于是是有有21212()()abqcq qc q q18 定定设设是是三三个个整

8、整. .则则理理数数若若, ,0| , | ,|2.a b cc a c bc ab 1212()abcqcqc qq 12| , | ,c a c bq q证证 因因所所以以存存在在整整数数使使得得 12,acqbcq 12,.qqc | ab因因是是整整数数 所所以以19 , ,0| , |3,.a b cc a c bs tc satb 设设是是三三个个整整数数. .若若则则对对任任意意整整数数 , ,有有 , , 定定理理 12121122,0|,(1,2, ),|.4ninnna aacc ains ssc s as as a 设设是是整整数数. .若若则则对对任任意意整整 数数,

9、,有有 定定 理理1212()()()satbs cqt cqc sqtq 12| , | ,c a c bq q证证 因因所所以以存存在在整整数数使使得得 12,acqbcq, ,s t于于是是对对任任意意整整数数 12,.sqtqc | satb因因是是整整数数 所所以以20 , ,0,| , | ., ,1,1.a b cc a c bs tsatbc 设设是是三三个个整整数数如如果果存存在在整整数数使使得得 则则 例例1.c 故故 | , | ,1,c a c bsatb证证 因因且且所所以以有有c | satb |1,c21 ,| ,|5,.a ba b b aab 设设都都是是非非

10、零零整整数数 定定理理, ,若若则则 12| ,| ,a b b aq q证证 因因所所以以存存在在整整数数使使得得 12,abqbaq.ab 从从而而12112()()abqaq qa q q 12,q q于于是是=1=112,q q因因是是整整数数, ,所所以以121,qq 练习：1. 设a，b是两个给定的非零整数，且有整数x，y使得ax+by=1.证明：若a|n且b|n，则ab|n2. 设 是整系数多项式。若d|b-c，则d|2021/8/22221110( ).nnnnf xa xaxa xa( )( )f bf c解答：1.证明：由n=n(ax+by)=(na)x+(nb)y,及ab

11、|na，ab|nb 得证。2.证明： 又 得证。 2021/8/22231111( )( )()().()nnnnnnf bf ca bcabca bc|jjd bc24二、素数二、素数( (质数质数) )及其判别法及其判别法 0112nnnnn设设整整数数， ，如如果果除除了了和和外外， 没没有有其其它它因因数数, ,则则 叫叫做做( (或或素素数数质质数数不不可可约约或或),),否否则则 叫叫定定数数 义义做做合合数数. . 0, 1,:,nnnp当当整整数数时时和和同同为为素素数数或或合合数数. .因因此此通通常常素素数数总总是是指指正正整整数数 用用注注表表示示. . 1. 素素数数2

12、5 ,1,6.npnppn 设设 是是一一个个正正合合数数是是 的的一一个个大大于于的的最最小小正正因因数数 则则 是是素素数数, , 理理且且 定定 p假假设设矛矛盾盾, ,所所以以 是是素素数数. . , 1,pqqp证证 若若 是是合合数数 则则存存在在整整数数使使得得 | ,| ,p nq n又又于于是是pn这这与与 是是 的的最最小小正正因因数数的的 2,.pnpn因因此此故故 ,1npn因因 是是合合数数是是 的的大大于于 的的最最小小正正因因数数, ,所所以以,n1 1存存在在整整数数使使得得 111npnpnn|.q p26整整数数为为素素数数的的判判别别法法 ,|7,npnp

13、nn 设设 是是一一个个正正整整数数 如如果果对对所所 定定有有的的素素数数都都有有则则理理是是素素数数. .Eratosthenes2.2.素素数数的的判判别别法法1(1(筛筛法法) )nn 1 1、求求不不超超过过 的的一一切切素素数数, ,只只须须把把不不超超过过的的素素数数的的倍倍数数划划去去即即可可. . ,pppaap 2 22 2 2 2、要要划划掉掉素素数数 的的倍倍数数, ,可可以以从从开开始始划划起起, ,因因对对于于每每一一个个小小于于的的合合数数它它的的最最小小素素因因数数, , 因因而而在在之之前前已已被被划划掉掉了了. .27100N 求求出出所所有有不不超超过过例

14、例2 2的的素素数数. . 100102,3,5,7,2,3,5,71,1 100 解解 小小于于等等于于的的所所有有素素数数为为划划去去的的倍倍数数和和 余余下下的的即即为为之之间间的的素素数数. .2814689101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979892357910029 1

15、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故故之之间间的的素素数数有有共共个个. .30 素素数数有有定定理理8 8无无穷穷多多个个. .这这是是不不可可能能的的. .故故素素数数有有无无穷穷多多个个. .kppp 证证() () 假假设设整整数数中中只只有有有有限限反反证证个个设设为为法法素素数数, ,令令1212， ， ， ， ， ， ，1knp pp，1212 inpikn 则则所所以以 是是合合数数. .( =1,2, ),( =1,

16、2, ),n于于是是 的的大大于于 1(1)ip, ppik的的最最小小正正因因数数 是是素素数数 这这里里某某个个 , , 12kp | p pp因因此此, ,1p |31三、欧几里得除法三、欧几里得除法(带余除法带余除法) () ,9,0a bbq ra = bq+ r,rb 设设是是两两唯唯一一个个整整数数, ,其其中中0,0,则则的的欧欧几几里里得得存存在在整整 定定理理数数, ,使使得得除除法法,qabrab不不完完全全商商其其中中 叫叫做做 被被 除除所所得得的的叫叫做做 被被 除除所所得得的的余余数数. ., q r存存在在证证 ( (的的) )性性 考考虑虑数数列列,bbbbb

17、b,-3 ,-2 ,- ,0, ,2 ,3,-3 ,-2 ,- ,0, ,2 ,3 ,a则则 必必在在上上述述数数列列的的某某两两项项之之间间q即即存存在在整整数数 , ,32a = bq+ rrb, 0, 0(1)qbaqb0abqb使使得得 ,rabq令令则则有有11,.q = qrr 故故从从而而11,q rq rqr( (的的) ) 若若有有整整数数 , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb若若则则而而矛矛盾盾. . 111,0, 0abqrrbabqrrb33 0,0,9,0|:|bbabqrrb如如果果将将条条件件改

18、改为为则则定定理理 注注中中结结论论可可改改为为|0.b aabr被被 除除所所得得的的余余数数推推论论 7, 由由定定理理 和和欧欧几几里里得得除除法法 可可得得判判断断一一个个整整数数是是否否为为素素数数的的方方法法. .137.N 例例3 3 证证明明为为素素数数 137122,3,5,7,11, 证证 因因小小于于等等于于的的素素数数有有34 2,3,5,7,11137,7,137N 所所以以皆皆不不能能整整除除由由定定理理 知知为为素素数数. .,NNNNN 对对于于整整数数, ,先先求求出出不不超超过过的的所所有有素素数数 若若这这些些素素 一一数数都都不不能能整整除除则则为为素素

19、般般地地, ,数数 否否则则为为合合数数. . 1376821,1374532,1372752,1371974,13712 115.又又 2021/8/22352021/8/223637 () ,10a bbcq ra = bq+ r,crbc 设设是是两两个个整整数数, ,其其中中0,0,则则对对任任意意整整数数 , ,存存在在唯唯一一的的整整数数, ,使使得得 欧欧几几里里 定定理理得得除除法法 欧欧几几里里得得除除法法的的推推广广形形式式, q r存存在在证证 ( (的的) )性性 考考虑虑数数列列,bcbcbc c bcbcbc,-3,-2,-, ,2,3,-3,-2,-, ,2,3

20、,a则则 必必在在上上述述数数列列的的某某两两项项之之间间q即即存存在在整整数数 , ,(1)qbcaqbccabqbc使使得得38a = bq+ rcrbc, , ,rabq令令则则有有11,.q = qrr 故故从从而而11,q rq rqr( (的的) ) 若若有有整整数数 , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb若若则则而而矛矛盾盾. . 111,abqrcrbcabqrcrbc39c对对定定理理1010中中 的的某某些些特特定定义义3 3 殊殊取取值值: : ,0,cbbrr 4.4.当当时时 有有这这时时 叫叫做做最

21、最大大负负余余数数. . 1.0,0,crbr当当时时 有有这这时时 叫叫做做最最小小非非负负余余数数. . 1,1,crbr2.2.当当时时 有有这这时时 叫叫做做最最小小正正余余数数. . 1,10,cbb+rr 3.3.当当时时 有有- -这这时时最最大大非非 叫叫做做 正正余余数数. . 5.2 ,.22bbbk ckkrk 当当时时 有有- - 2 ,1,.22bbbk ckkrk 当当时时 有有- -40 21,bkck 当当时时 有有11.222bbbbkrk -2 2112bbkrk -1-1-=-=2 2即即,b于于是是无无论论 取取偶偶数数还还是是奇奇数数 总总有有.22b

22、bbbrr- - 或或 - -2222r绝绝对对值值最最这这时时 叫叫做做小小余余数数. .2021/8/22412021/8/22424322221444433336332)133|11123 7|33334444nnnnn 1 1、若若nZ,nZ,求求证证：1)33|1)33|）思考题思考题作业2112)2| (1)(31)3)9|(31)7125 2141nnn nnppp 2n2n1 1、若若nZ,nZ,求求证证：1)168|131)168|13、设设素素数数，是是素素数数，则则是是合合数数。441.2 1.2 整数的表示整数的表示 11101,01,1,21, ,0.kkkkiikb

23、nna baba baaabika 设设 是是大大于于 的的正正整整数数 则则任任唯唯一一意意正正整整数数都都可可地地表表成成其其中中 是是整整数数且且首首 定定理理项项系系数数证证 由由欧欧几几里里得得除除法法 000,01nbqaab 0111,01qbqaab45 122221111,01,01,01kkkkkkkkqbqaabqbqaabqbqaab 注注意意到到12100kkqqqqqn (1,2,),0.ikqikq因因为为整整数数 所所以以必必有有整整数数使使得得1.kkqa 于于是是上上述述等等式式中中最最后后一一个个等等式式为为46 ,从从最最后后一一个个等等式式开开始始 依

24、依次次代代入入上上一一等等式式, ,即即得得 1110kkkkna baba ba :n如如果果 有有两两种种不不同同的的表表示示式式 11101110,01,1,01,1,kkkkikkkkina baba baabiknc bcbc bccbik (00)kkac这这里里可可以以取取或或471111100()()()()0kkkkkkacbacbac bac 上上两两式式相相减减, ,得得 ,jjiiacijac设设而而当当时时则则有有11()()()0jkjkkjjjjbacbacbac 110,()()()0kjkkjjjjbacbacbac 因因所所以以有有 111()()kjjjk

25、kjjacacbacb 因因此此有有 48|()jjbac 于于是是 |jjacb 01,01jjabcb但但 |,jjacb又又有有矛矛盾盾. .n故故 的的表表示示式式是是唯唯一一的的. . 11011101101()01,0,1,2, ,0.().kkbkkkkikkkbna aa ana baba baabik anba aa an 用用表表示示展展开开式式其其中中称称为为整整数数 的的 进进 定定制制表表示示义义49 1 每每个个正正整整数数都都可可以以表表成成不不同同的的2 2 推推论论的的幂幂的的和和. .0321264211602321102101221225052100102

26、200202400402800802160例例1 表示整数表示整数642为二进制为二进制因为：因为： 2642(1010000010) 所所以以5011111111F1515011101117 77 711101110E1414011001106 66 611011101D1313010101015 55 511001100C1212010001004 44 410111011B1111001100113 33 310101010A1010001000102 22 2100110019 99 9000100011 11 1100010008 88 8000000000 00 0二进制二进制十六

27、进制十六进制十进制十进制二进制二进制十六进制十六进制十进制十进制二进制二进制, ,十进制和十六进制换算表十进制和十六进制换算表51 一般地一般地, ,将十进制转换为二进制比转换为十六将十进制转换为二进制比转换为十六进制要容易些进制要容易些. .因此要将十进制转换为十六进制因此要将十进制转换为十六进制, ,可先将十进制转换为二进制可先将十进制转换为二进制, ,再将二进制转换为十再将二进制转换为十六进制六进制.(.(四四位二进制数对应一个十六进制位二进制数对应一个十六进制数数) )321610(ABC8)10 1611 1610 168 (43976) 例例2 2 2222 A(1010) ,B(

28、1011) , C(1100) ,8(1 0,30 0) 例例因因162101(ABC8)(101100110)0010 所所以以 102161040010 (642)(10)00(282例例1.3 1.3 最大公因数与广义欧几里得除法最大公因数与广义欧几里得除法一、最大公因数一、最大公因数52 1212,(2),|(1,2, ),.1nkna aan nd aknda aa 设设是是个个整整数数 若若整整数数则则称称 是是的的一一个个 定定公公因因数数义义 121212,(,).nnna aaa aaa aa 若若不不全全为为零零, ,则则整整数数的的所所有有公公因因数数中中最最大大的的一一

29、个个公公因因数数叫叫做做记记作作最最大大公公因因数数. . 1212,(,)1,nna aaa aa 互互素素特特别别 当当时时 称称或或互互质质. .53 1212120,( ),;(2)|,|.nnnda aad | a d | ad | ae a e | ae | ae d 是是的的最最大大公公因因数数1 1 若若则则最最大大公公因因数数可可描描述述为为: : (14,21)7, ( 15,21)3, (14, 15,211.1)例例 2,( , )( , ).a bb aa b 设设是是两两个个例例整整数数 则则 ,| ,3( , ).a bb aa bb 设设是是两两个个正正整整数数

30、 如如果果则则例例54 ,|,papapa 设设 是是一一个个素素数数, , 为为 整整数数 如如果果则则例例与与4 4互互素素. .:素素数数与与任任一一整整数数有有如如下下关关系系 ,| .| ,|,dpd ap apa 若若则则因因于于是是与与题题设设矛矛盾盾 ( , ),|,1.p addppdp 证证 设设则则有有因因 是是素素数数 所所以以或或 1,( , )1.dp a故故必必 从从而而 |,|,|( , ).dd ab d abda b若若 为为 练练习习奇奇数数，则则55 (1)|,1,|,1.iid aindain证证设设则则有有1212,|,|,|nna aaaaa故故的

31、的公公因因数数也也是是的的公公因因数数. . ,|,1,|,1.iidaind ain反反之之 设设同同样样有有1212|,|,|,nnaaaa aa故故的的公公因因数数也也是是的的公公因因数数. . (2)(1)(2).由由即即得得 1212121212,( ),|,|,|;(2) (,)(|,|,|).1nnnnna aana aaaaaa aaaaa 设设是是 个个不不全全为为零零的的整整数数 则则1 1与与的的公公因因数数相相 定定理理同同 56 ,( , )(, )( ,)(|,5|).a ba ba babab 设设是是两两个个整整数数 则则例例有有 .2,()bb = b设设 是

32、是任任一一正正整整数数 则则 0,0,定定理理 (0,21)21, ( 156,0)15, (0, ) | .bb例例 0,(0, ).bbbb 证证 因因任任何何非非零零整整数数都都是是 的的因因数数 而而正正整整数数的的最最大大因因数数为为故故 如何才能计算出两个整数的最大公因数哪？(*)方法1：直接分解两个整数但当整数很大时不可行不可行(后面我们会讲到大整数分解是很困难的事情)方法2：广义欧几里得算法广义欧几里得算法/辗转相除法辗转相除法2021/8/225758.dd ,.db cdd 所所以以 是是的的公公因因数数 从从而而 ,.da bdd 同同理理可可证证, ,是是的的公公因因数

33、数 因因而而故故 18591 1573286, 1573528614 ,73例例因因(1859,1573)(1573,286)(286,143)143所所以以 , ,( , )( , ).a b ca = bq+ cqa b = b c设设是是三三个个不不全全为为零零的的整整数数 如如果果其其中中 是是整整数数则则 定定理理3 3 ( , ), ( , ),a bdb cdd | a d | b证证 设设则则于于是是|()| ,d aq bd c 59二、广义欧几里得除法二、广义欧几里得除法 111,0nnnnnrr qrr 01,.a bra rb设设是是任任意意两两个个正正整整数数 记记反

34、反复复运运用用欧欧几几里里得得除除法法: : 011221,0,rr qrrr 122332,0,rr qrrr 2111,0,nnnnnnrrqrrr 12110,0.nnnrrrrbnr 因因为为所所以以经经过过有有限限步步骤骤, ,必必存存在在使使得得60 011223113,( , )( ,)( ,)( ,)(,)(,)(,0)nnnnnna br rr rr rrrr rrr 于于是是由由定定理理 可可知知 ,( , ).4nna bra br 设设是是任任意意两两个个正正整整数数是是广广义义欧欧几几里里得得除除法法中中最最后后一一个个 定定理理非非零零余余数数 则则. 上上述述求求

35、两两个个整整数数的的最最大大公公因因数数的的方方法法叫叫做做也也叫叫广广义义欧欧几几里里得得除除法法, ,辗辗转转相相除除法法做做求最大公因数的步骤(*)：2021/8/226162 1859,81573,( , ).aba b 计计算算例例设设 18591 1573286157352862862 143143解解 因因( 1859,1573)(1859,1573)143.所所以以 46480,39423,( , ).aba b计计算算例例设设9 9解解 法法一一：最最小小非非负负余余数数4648013942370573942357057413863 522122 1 705714138291

36、94138129191219 29192 121948112192481257 4811257224257122433 22463326331267 263757152 (46480, 39423)1. 所所以以 6439423670572919 705722919121929192 1219481 12193481224481222433 224733733572 732122 1法法二二：绝绝对对值值最最小小余余数数464801394237057 (46480, 39423)1. 所所以以 651nnnrr q 0112,rr qr1223,rr qr211,nnnnrrqr在在广广义义欧

37、欧几几里里得得除除法法中中, ,由由3221,nnnnrrqr211,nnnnrrqr 1322,nnnnrrrq3122,rrr q2011rrr q( , )satba b1232, ,nnrrr rs t逐逐次次消消去去可可找找到到整整数数使使得得66 1859,1573, ,( , )1.0abs tsatba b 设设求求整整数数使使得得 例例 18591 1573286157352862862 143143解解 因因( , )143.s =t =sa + tb = a b 所所以以有有整整数数5,6,5,6,使使得得 1573528615735(18591 1573143) 于于是

38、是 1573528628618591431 1573 5( 1859)6 1573 67 ,( , )0,1,2,5,nnnna bs at ba bnst 设设是是任任意意两两个个正正整整数数, ,则则对对于于这这里里归归 纳纳 定定理理地地定定义义为为 01211012111,0,0,0,jjjjjjjjssssqsttttqt 2,3,jn jq其其中中是是广广义义欧欧几几里里得得除除法法中中的的不不完完全全商商. . :0,1,2,jjjjjns at brr 只只需需证证明明 对对于于其其中中 是是广广义义欧欧几几里里得得除除 法法中中分分析析: :的的余余数数. . ( , )nn

39、ns at bra b ,jn 当当时时 就就有有68 0000001,0,0j =sts at barj 时时, ,由由题题设设以以及及知知结结论论对对于于成成立立. . j对对 作作数数学学归归纳纳法法. . 1111110,1,1j =sts at bbrj 时时, ,由由题题设设以以及及知知结结论论对对于于成成立立. . 11,jjjjks at br假假设设结结论论对对于于成成立立 即即69 211,kkkkjkrrrq 对对于于有有,由由归归纳纳假假设设 可可得得211211()()kkkkkksqsatqtb 21122111()()kkkkkkkkkrrrqsatbsatb q

40、kks at bjk 结结论论对对于于也也成成立立. . j由由数数学学归归纳纳法法原原理理, ,结结论论对对于于所所有有的的 成成立立. .70 5,( , )s tsatba b 由由定定理理 及及其其证证明明 可可得得求求整整数数使使得得的的方方法法. . 010101,1,00,1rarbsstt ,首首先先 令令 100(1)0,rsstt 如如果果则则令令.计计算算结结束束71 01201 11,rqrrq rr否否则则, ,计计算算 211(2)0,rsstt 如如果果则则令令.计计算算结结束束否否则则, ,计计算算 12312 22,rqrrq rr 201 1201 1,ss

41、q sttq t以以及及 72 11(3)0(3),jjjrjsstt如如果果则则令令否否则则, ,计计算算 111,jjjjjjjrqrrq rr 211211,jjjjjjjjssqsttqt以以及及 10,nr 最最后后, ,一一定定有有这这时时, ,令令 ,nnsstt.计计算算结结束束73ja(r0) b(r1)101100123njq1q2q3qnqjr1jr 1r2r2r3r3r4rnr1nr 1js js2s2s1s3s1ns ns1jt jt1t2t2t3t1nt nt2q 2q :上上述述过过程程可可以以列列表表如如下下|t|s|(,)a b|074 111211211jj

42、jjjjjjjjjjjjjrqrrrq rssqsttqt 1,2,jn 2,3,jn 010101,1,00,1rarbsstt ,其其中中75j 0123456 737,635, )11(abs tsatba b设设计计算算整整数数使使得得例例jqjr1jr 1js js1jt jt63573763510635110210011026230111 2311 410106 6 77233252529 29 31156 56 656530193224 |t|s|( , )a b76193737( 224)6351 所所以以 5, , ,s t dsatbdda b定定理理 的的逆逆命命题题不不

43、成成立立 即即若若有有整整数数使使 注注: : 但但 未未必必是是的的最最大大公公因因数数. . ( , )1, ,61a bs tsatb存存在在整整数数使使得得定定理理 ,|1,( , )1.d | sa + tbda b = d 所所以以 于于是是因因此此 5.证证 由由性性定定理理要要即即得得必必 ( , ),| ,| ,d = a bd a d b充充分分性性 设设则则因因sa + tb =1 1是否也有是否也有(a，d)=1和和(b，c)=1？2021/8/227778 ,():(1)| ,| ;(2)| ,| ,|.abdd = a,bd a d be a e be d 定定 设

44、设 ， 是是任任意意两两个个不不全全为为零零的的整整数数是是正正整整数数 则则的的是是若若则则要要理理充充条条件件7 7 ( , ),| ,| .da bd a d b 证证 若若则则显显然然 5, ,s tsa + tb = d由由定定理理存存在在整整数数使使得得 | , | ,|,|.e a e be satbe d 于于是是若若则则因因而而 ,(1),da b反反之之 若若成成立立 则则 是是的的公公因因数数; ;79 (2),|,|,a be ded 则则若若成成立立的的任任一一公公因因数数于于是是 ,da b因因此此是是的的最最大大公公因因数数. .7(1)(2):定定理理 中中条条

45、件件和和可可以以作作为为最最大大公公因因注注数数的的定定义义. . , (1)(,)( , ).( , )(2)| ,| ,(,).|(,)1.( , ) ( , )abmam bma b ma ba bdd a d bd ddaba ba b 设设 ， 是是任任意意两两个个不不全全为为零零的的整整数数. .若若是是任任一一正正整整数数 则则 若若非非零零整整数数 满满足足则则 特特别别地地, , 定定理理8 880|.ddm于于是是 ( , ),(,),da bdam bm 证证 (1) (1)设设则则存存在在整整satbd ,()()ms amt bmdm两两端端同同乘乘以以得得 | ,|

46、 ,|,|,d a d bdm am dm bm又又因因|,dm d .mddmd = d而而和和都都是是正正整整数数, ,所所以以即即( , )(,).a b mma mb , ,s t数数使使得得81 (,)|ab=ddd (2)| ,|,(1)d a d b当当时时 由由有有 ( , )(|,|)(,)|ababa b =ddddddd ( , ), (,).|aba bddd 因因此此 ,( , ),da b 特特别别地地 取取时时 有有 (,)1.( , )( , )aba ba b 82 11 200306,23 200306,( , )12.aba b计计算算 例例设设(11,2

47、3) 200306200306 (11,23)1, 解解 因因所所以以( , )(11200306,23200306)a b 12,:nna aa个个整整数数的的最最大大公公因因数数的的求求法法 121122233112,0,(,), (,),(,)(,).nnnnnna aanaa addaddada aad 设设是是 个个整整数数, ,且且令令则则 定定理理9 9 83 (120 150 210 35). 计计算算最最大大公公因因数数，例例1313 (120,150)(4, 5) 3030解解 因因(30,210)30 (30,35)5 (120 150 210 35)5. 所所以以, ,

48、最最大大公公因因数数 ，最最后后介介绍绍几几个个与与最最大大公公因因数数有有关关的的结结论论：欧几里得除法的应用：2021/8/2284 ,(21 21)1( , )10aba ba b 设设是是两两个个正正整整数数 则则 , ,定定理理=1.=1. ,2121211.abra babr 设设是是两两个个正正整整数数 若若 被被 除除的的最最小小正正余余数数是是 , ,则则被被除除的的最最小小 引引理理正正余余数数是是( , ),111.aba ba b 设设是是两两个个正正整整数数, ,则则2 2和和2 2的的最最 引引理理2 2大大 公公因因数数是是2 285 ,2121211.abra

49、babr 设设是是两两个个正正整整数数 若若 被被 除除的的最最小小正正余余数数是是 , ,则则被被除除的的最最小小 引引理理正正余余数数是是1(21)(21)brq, ,a bq r证证 对对用用欧欧几几里里得得除除法法, ,存存在在整整数数使使得得 ,1abqrrb2121abq r 于于是是 2 21bqr2 (21)(21)rbqr(1)12 (21),rb qq 其其中中为为整整数数知知结结论论成成立立. .86( , ),111.aba ba b 设设是是两两个个正正整整数数, ,则则2 2和和2 2的的最最 引引理理2 2大大 公公因因数数是是2 2, a b证证 对对用用广广义

50、义欧欧几几里里得得除除法法, ,得得 1111222123332111,0,0,0,0( , )nnnnnnnnnabqrrbbr qrrbrr qrrbrrqrbrrrarbq 87 11231221112321(21)(21)21(21)(21)21(21)(21)21(21)()21(21)21nnnnnrabrrbrrrrrnrrnrppppp 由由引引理理1 1 1121,nppp 其其中中是是整整数数. . (21, 21)21nrab由由广广义义欧欧几几里里得得除除法法知知, ,88 ,(21 21)1( , )10aba ba b 设设是是两两个个正正整整数数 则则 , ,定定

51、理理=1.=1.2证证 由由引引理理 即即得得结结论论. . 11,21| 21|baa bb a设设是是两两个个正正整整数数 则则 定定理理. . , 0abqrrb证证 设设 121(21)(21), 02121abrrbq由由引引理理1 1的的证证明明可可得得891212 (2 )(2 )1).rbqbqq其其中中为为整整数数 |b a. .r 221| 2110ba于于是是 0r 1.4 1.4 整除的进一步性质及最小公倍数整除的进一步性质及最小公倍数一、整除的性质一、整除的性质90 , ,0,0.( , )(, )( ,1)a b cbca cab cb c 设设是是三三个个整整数数

52、, ,且且如如果果1,1,则则 定定理理 ,( , )1, ,1a cs tsatc 反反之之 因因于于是是存存在在整整数数使使得得 (, ),( , ).| ,| .dab cdb cdb dc证证 令令则则有有 |,| .|.dab dcdd于于是是有有从从而而91 ,()()bs abtb cb两两端端同同乘乘以以得得 |,| ,| ()() ,| .d ab d cd s abtb cd b 由由可可得得即即有有|.d d于于是是.dd 故故 , ,0,|,( , )1,| .a b ccc aba cc b 设设是是三三个个整整数数 且且如如果果 则则 推推论论|(, )( , ),

53、cab cb c 证证 由由题题设设条条件件及及定定理理1,1,有有| .c b从从而而92 ,|,2| .pp abp ap b定定设设 是是数数 若若则则或或理理素素 |,1| .p abp b又又因因由由定定理理 之之推推论论有有 |,( , )1.pp ap a 证证 因因 是是素素数数, ,所所以以若若则则2021/8/2293 , ,( , )1,( , )13,(, )1.a b ca cb cab c 设设是是整整数数 若若则则 定定理理1,(, )( , )1.ab cb c证证 由由题题设设及及定定理理 有有1212,(, )1,1,(, )1.nina aaca cina

54、 aac 推推广广: :设设是是整整数数 如如果果则则94 1212,|,|.nnka aapp a aapa 设设是是整整数数是是素素 推推论论数数. .如如果果则则某某个个 |,(, )1,1iippaapin 证证( (反反证证法法) ) 因因 是是素素数数, ,所所以以若若则则12(, )1.na aap 于于是是有有 12|.np a aa与与题题设设 矛矛盾盾练习：设k是正整数，证明： (1)(ak, bk)=(a, b)k (2)设a，b是正整数，若(a，b)=1，ab=ck，则a=(a, c)k，b=(b, c)k提示： (a, b)=1(ak-1, b)=1 a=a(ak-1

55、, b)=(ak, ab)=(ak, ck)2021/8/229596二、最小公倍数二、最小公倍数 1212121212,|,|,|,.nnnnna aanam amamma aaa aaa aa设设是是 个个整整数数 若若则则 叫叫做做的的一一个个. . 的的所所有有公公倍倍数数中中最最小小正正整整数数叫叫做做记记作作定定义义公公倍倍数数最最小小公公倍倍数数1 1 12,(1)|, 1;(2)|, 1,|.niima aaaminaminm m 若若则则:易易知知97 ,(1)|,|,|;(2) ,.4a ba m b mab ma bab 设设是是两两个个互互素素的的正正整整数数 则则若若

56、则则定定理理.mabt 于于是是|,a mmak 证证 (1) (1) 因因, ,则则|,|,b mb ak又又即即( , )1,| ,a bb k 而而所所以以,kbt 由由此此可可得得|.ab m故故 (2),|,|aba ba m b m显显然然是是的的公公倍倍数数. .又又若若, , (1)|.ab m由由,aba b所所以以是是的的最最小小公公倍倍数数 故故 , .a bab 98123123,a aaa aa 于于是是 121212(,)1,4,.a aa aa a证证 因因 由由定定理理 12,na aan设设是是 个个两两两两互互素素的的正正整整 推推数数 广广即即 1212(

57、,)1,1,.ijnna ai jnija aaa aa , ,则则 1323123(,)(,)1,(,)1,a aaaa aa又又由由定定理理3,3,123123,.a aaa a a ,如如此此继继续续 可可得得 1212,.nna aaa aa 99 ,(1) , . , ( , ).( , )(2)|,|, , |.5a baba ba b a baba ba m b ma bm设设是是两两个个正正整整数数 则则即即若若则则定定理理, ,a b对对于于一一般般的的正正整整数数有有 12.( , )( , )abkka ba b,ma b证证 (1) (1)设设是是的的一一个个公公倍倍数

58、数, ,那那么么存存在在整整1212,k kmak mbk数数使使得得因因此此12,akbk 100(,)1.( , ) ( , )aba ba b 由由于于 1|,( , )bka b所所以以有有1,.( , )bkt ta b 即即有有为为某某个个整整数数1,( , )abmakta b于于是是,( , )abtta ba b另另一一方方面面, ,对对任任意意的的整整数数 , ,显显然然是是的的公公,( , )aba bmmta b 所所以以的的任任一一公公倍倍数数可可表表成成的的形形式式. .倍倍数数. .1011,t 当当时时 得得到到最最小小公公倍倍数数 , ( , )aba ba

59、b 任任意意两两个个正正整整数数的的乘乘积积等等于于这这两两个个数数的的最最小小公公倍倍数数与与最最大大公公因因数数的的乘乘积积. .这这两两个个数数的的最最小小公公倍倍数数不不但但是是最最小小的的正正倍倍数数, ,且且是是另另外外的的公公倍倍此此定定理理表表明明: :数数的的因因数数. . , , ()( , )abmta b tta b为为整整数数 (2)(1), a bm由由的的证证明明可可知知, ,的的任任一一公公倍倍数数可可表表成成 , |.a bm所所以以102, , , .m a bma mbm a b 推推论论 设设是是正正整整数数 则则 , .m a b 2,(,)m abm

60、a mbma mb 证证 2( , )m abm a b ( , )abma b 12122233112,6,nnnnnna aana ammammama aam 设设是是 个个整整数数 令令,则则 = =定定理理. . , , .1p qp qpq 设设是是两两个个不不同同的的素素数数 则则例例103 120,150,210,35.2 计计算算最最小小公公倍倍数数例例4 5120,1504,5 3030600(4,5) 解解 因因20 7600,21020,7 30304200(20,7) 4200,35120,1 35120 354200120,150,210,354200. 故故 104 121