信息安全数学基础(第一章)2014-2015下

1、1信息安全数学基础信息安全数学基础 王骞王骞 武汉大学计算机学院武汉大学计算机学院2一、信息安全数学基础的内容一、信息安全数学基础的内容 内容： 初等数论、近世（抽象）代数、椭圆曲线 方式：课堂教学为主 目的：了解和掌握数论和代数的基本知识，包括整数整数 的可除性的可除性 、同余、同余式、二次同余式与平方、同余、同余式、二次同余式与平方 剩余剩余 、原根、原根、群、环、域群、环、域和和椭圆曲线椭圆曲线等等二、教学方式和目的二、教学方式和目的3三、数论和代数在信息安全中的作用三、数论和代数在信息安全中的作用 例：公钥密码学（Public-key cryptography）所基于的三个难解数学问题

2、: 1. 大因数分解问题（RSA加密(签名) 安全基础） 2. 离散对数问题 3. 椭圆曲线离散对数问题 都涉及数论、代数和椭圆曲线论中的部分知识。 信息安全数学基础 - 密码学基础 - 网络（信息）安全基础4三、课程考核三、课程考核 闭卷考试+作业四、成绩计算四、成绩计算 平时作业30% + 考试70% 五、教材和参考书目五、教材和参考书目1信息安全数学基础，清华大学出版社，陈恭亮信息安全数学基础，清华大学出版社，陈恭亮2信息安全数学基础清华大学出版社，覃中平、张 焕国看书时注意书中的书写错误。看书时注意书中的书写错误。5第一章第一章 整数的可除性整数的可除性要求：要求：掌握整除、素数、最大

3、公因数等的定义，熟练运用欧几里得除法和广义欧几里得除法。 61.1 1.1 整除的概念整除的概念 欧几里得除法欧几里得除法一、整除基本概念及性质一、整除基本概念及性质 1.1,.10|a bbqabqbaabb a 设设是是任任意意两两个个整整数数, ,其其中中如如果果存存在在一一个个整整数数 使使得得等等式式成成立立, ,则则称称或或者者 被被 整整除除, ,记记作作除除 义义整整 定定如如果果 不不能能整整除除则则记记作作,|.baba 因因数数如如果果则则 叫叫做做 的的而而 叫叫做做 的的倍倍数数| ,.b abaab写写成成或或/.aa bb此此时时 可可q7 当当 遍遍历历整整数数

4、 的的所所有有因因数数时时也也遍遍历历整整数数 的的所所有有因因数数(2), /.baa ba 当当 遍遍历历整整数数 的的所所有有因因数数时时也也遍遍历历整整数数 的的因因注注所所有有数数(1),:.baba 对对任任何何整整数数有有(5)0,| .aa a 对对任任何何整整数数有有(3)0,| 0.bb 对对任任何何整整数数有有1 1| |(4),.bb 若若则则(6)| ,|(),()|().b ababa 8 1,0,0| , | ,| .1.1a bcc b b ac a 设设是是三三个个整整数数. .若若则则定定理理12, | .q qc a因因是是整整数数 所所以以12|c bb

5、 aqq证证 设设，则则存存在在整整数数 ， ，使使得得12bcqabq ，于于是是有有21212()()abqcq qc q q 9 1.1.2, ,0| , | ,|.a b cc a c bc ab 设设是是三三个个整整数数. .理理若若定定则则1212()abcqcqc qq 12| , | ,c a c bq q证证 因因所所以以存存在在整整数数使使得得 12,acqbcq 12,.qqc | ab 因因是是整整数数 所所以以10 1.1.3, ,0| , | ,|.a b cc a c bs tc satb 设设是是三三个个整整数数. .若若则则对对 任任意意整整数数 , , ,

6、,定定理理有有 12121122,0|,(1,2, ),1.1|.4.ninnna aacc ains ssc s as as a 设设是是整整数数. .若若则则对对任任意意整整数数, ,有有 定定 理理 1212()()()satbs cqt cqc sqtq 12| , | ,c a c bq q证证 因因所所以以存存在在整整数数使使得得 12,acqbcq, ,s t于于是是对对任任意意整整数数 12,.sqtqc | satb 因因是是整整数数 所所以以11 , ,0,| , | ., ,1,1.1.1.1a b cc a c bs tsatbc 设设是是三三个个整整数数如如果果存存在

7、在整整数数使使得得 则则 例例1.c 故故 | , | ,1,c a c bsatb 证证 因因且且所所以以有有c | satb |1,c12 1.1.5,| , | ,.a ba b b aab 设设都都是是非非零零整整数数, ,若若则则 定定理理 12| , | ,a b b aq q证证 因因所所以以存存在在整整数数使使得得 12,abqbaq .ab 从从而而12112()()abqaq qa q q 12,q q于于是是=1=112,q q因因是是整整数数, ,所所以以121,qq 13二、素数二、素数( (质数质数) )及其判别法及其判别法 1.1.2011nnnnn 设设整整数数

8、， ，如如果果除除了了和和外外， 没没有有其其它它因因数数, ,则则 叫叫做做( (或或素素数数质质数数不不可可约约或或) ), ,否否则则 叫叫定定 数数 义义做做合合数数. . 0, 1,:,nnnp 当当整整数数时时和和同同为为素素数数或或合合数数. .因因此此通通常常素素数数总总是是指指正正整整数数 用用注注表表示示. . 1. 素素数数14 1.1.6,1,.npnppn 设设 是是一一个个正正合合数数是是 的的一一个个大大于于的的最最小小正正因因数数 则则 是是素素数数, ,且且 定定理理 p假假设设矛矛盾盾, ,所所以以 是是素素数数. . , 1,pqqp 证证( () ) 若

9、若 是是合合数数 则则存存在在整整数数反反证证法法使使得得 | ,| ,p nq n又又于于是是pn这这与与 是是 的的最最小小正正因因数数的的 2,.pnpn 因因此此故故 ,1npn因因 是是合合数数是是 的的大大于于 的的最最小小正正因因数数, ,所所以以,n1 1存存在在整整数数使使得得 111nnpnpn|.q p15整整数数为为素素数数的的判判别别法法 1,|.1.7,npnp nn 设设 是是一一个个正正整整数数 如如果果 定定理理对对所所有有的的素素数数都都有有则则 是是素素数数. .1. 1.1.72. 1 对于比较小的整数，利用定理可以迅速判断出它是否为素数。 每个不等于

10、的整数都有一个注：素因数。1.1.61.1.6,1( | )nppnpnn . .证证：反反证证法法（素素数数满满足足条条件件，排排除除合合数数可可能能）. .假假设设为为合合数数，题题设设和和定定理理相相矛矛盾盾. .因因为为根根据据定定理理它它的的大大于于 的的最最小小正正因因数数是是素素数数，且且因因此此，为为素素数数，且且满满足足假假设设条条件件. .16Eratosthenes2 2. .素素数数的的求求法法( (筛筛法法) )nn 1 1、要要求求出出不不超超过过 的的一一切切素素数数, ,只只须须把把不不超超过过的的素素数数的的倍倍数数划划去去即即可可. . ,pppaap 2

11、22 2 2 2、要要划划掉掉素素数数 的的倍倍数数, ,可可以以从从开开始始划划起起, ,因因对对于于每每一一个个小小于于的的合合数数它它的的最最小小素素因因数数, , 因因而而在在之之前前已已被被划划掉掉了了. .17100N 求求出出所所有有不不超超过过例例2 2的的素素数数. . 100102,3,5,7,2,3,5,71,1 100 解解 小小于于等等于于的的所所有有素素数数为为划划去去的的倍倍数数和和 余余下下的的即即为为之之间间的的素素数数. .18146891011121314151617181920212223242526272829303132333435363738394

12、04142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979892357910019 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故故之之间间的的素素数数有有共共个个. .201.1.8 素素数数有有无无定定理理穷穷多多个个. .这这是是不不可可能能的的. .故故素素数数

13、有有无无穷穷多多个个. .kppp 证证( () ) 假假设设整整数数中中只只有有有有限限反反证证个个设设为为法法素素数数, ,令令1 12 2， ， ， ，1knp pp ，1 12 2 inpikn 则则所所以以 是是合合数数. .( ( = =1 1, ,2 2, , , ) ), ,n于于是是 的的大大于于 1(1)ip, ppik 的的最最小小正正因因数数 是是素素数数 这这里里某某个个 , , 12|kp| p ppp n因因此此（又又）, ,11.1.3p|（定定理理）21Comment-1：尚未找到产生素数的有效公式， 寻找大素数需要借助计算机Comment-2：假设某一个大数

14、是两个素数的乘积（e.g.,1024 bits）,找到这两个素数是一个困难问题，即大数分解问题。22三、欧几里得除法三、欧几里得除法(带余除法带余除法) () ,1.1.9,0a bbqrra = b + ,rbq 设设是是两两个个整整数数, ,其其中中0,0,则则存存在在欧欧几几里里得得 定定唯唯一一除除的的得得法法理理整整数数, ,使使,qabrab不不完完全全商商其其中中 叫叫做做 被被 除除所所得得的的叫叫做做 被被 除除所所得得的的余余数数. ., q r存存在在证证 ( (的的) )性性 考考虑虑数数列列,bbbbbb, ,- -3 3 , ,- -2 2 , ,- - , ,0

15、0, , , ,2 2 , ,3 3 ,a则则 必必在在上上述述数数列列的的某某两两项项之之间间q即即存存在在整整数数 , ,23a = bq+ rrb, 0, 0(1)qbaqb0abqb使使得得 ,rabq令令则则有有11,.q = qrr 故故从从而而11,q rq rqr( (的的) ) 若若有有整整数数 , , 和和, ,唯唯一一性性使使得得11().b qqrr 111,| ()|,|,qqb qqbrrb 若若则则而而矛矛盾盾. . 111,0, 0abqrrbabqrrb 24 0,0,1.1.9,0|:bbabqrrb如如果果将将条条件件改改为为则则定定理理中中结结论论可可改

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

17、则则为为合合数数. . 13768 2,13745 3,1372712245,13719 7,137121. 51 又又 26 ) (1.1.1,0a bbcq ra = bq+ r,crbc 设设是是两两个个整整数数, ,其其中中0 0, ,则则对对任任意意整整数数 , ,存存在在唯唯一一的的整整欧欧几几里里数数, ,使使 定定理理除除法法得得得得欧欧几几里里得得除除法法的的推推广广形形式式, q r存存在在证证 ( (的的) )性性 考考虑虑数数列列,bcbcbc c bcbcbc , ,- -3 3, ,- -2 2, ,- -, , , , ,2 2, ,3 3 ,a则则 必必在在上上

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

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

20、是奇奇数数 总总有有.22bbbbrr- - 或或 - -2222r绝绝对对值值最最这这时时 叫叫做做小小余余数数. .301.2 1.2 整数的表示整数的表示 11101,01,1,2, ,0.1.2.1kkkkiikbnna baba baaabika 设设 是是大大于于 的的正正整整数数 则则任任意意正正整整数数都都可可唯唯一一地地表表成成其其中中 是是整整数数且且首首项项系系 理理数数 定定证证 （）由由欧欧几几存存在在性性里里得得除除法法 000,01nbqaab 0111,01qbqaab 31 122221111,01,01,01kkkkkkkkqbqaabqbqaabqbqaa

21、b nb注注意意到到 和和 都都为为正正整整数数，12100kkqqqqqn -1(1,2,),0().ikkqiqbkq 因因为为整整数数 当当时时，必必有有整整数数使使算算法法停停止止得得1.kkqa 于于是是上上述述等等式式中中最最后后一一个个等等式式为为32 ,从从最最后后一一个个等等式式开开始始 依依次次代代入入上上一一等等式式, ,即即得得 1110kkkkna baba ba :n（）如如果果 有有两两种种不不同同的的一一性性表表示示式式唯唯 11101110,01,1,01,1,kkkkikkkkina baba baabiknc bcbc bccbik (00)kkac 这这

22、里里可可以以取取或或331111100()()()()0kkkkkkacbacbac bac 上上两两式式相相减减, ,得得 ,0,jjiiacij jac 设设而而当当（时时就就是是原原式式）时时则则有有11()()()0jkjkkjjjjbacbacbac 110,()()()0kjkkjjjjbacbacbac 因因所所以以有有 111()()kjjjkkjjacacbacb 因因此此有有 34|()jjbac 于于是是 |jjacb 01,01jjabcb 但但 |,jjacb又又有有矛矛盾盾. .n故故 的的表表示示式式是是唯唯一一的的. . 11011101101()01,0,1,

23、2, ,0.(.2).1kkbkkkkikkkbbna aa ana baba baabik ana aa an 用用表表示示展展开开式式其其中中称称为为整整 数数 定定义义表表示示的的 进进制制35 1 每每个个正正整整数数都都可可以以表表成成不不同同的的2 2 推推论论的的幂幂的的和和. .0321264211602321102101221225052100102200202400402800802160例例1 表示整数表示整数642为二进制为二进制因为：因为： 2642(1010000010) 所所以以3611111111F1515011101117 77 711101110E14140

24、11001106 66 611011101D1313010101015 55 511001100C1212010001004 44 410111011B1111001100113 33 310101010A1010001000102 22 2100110019 99 9000100011 11 1100010008 88 8000000000 00 0二进制二进制十六进制十六进制十进制十进制二进制二进制十六进制十六进制十进制十进制二进制二进制, ,十进制和十六进制换算表十进制和十六进制换算表37 一般地一般地, ,将十进制转换为二进制比转换为十六将十进制转换为二进制比转换为十六进制要容易些进制

25、要容易些. .因此要将十进制转换为十六进制因此要将十进制转换为十六进制, ,可先将十进制转换为二进制可先将十进制转换为二进制, ,再将二进制转换为十再将二进制转换为十六进制六进制.(.(四位二进制数对应一个十六进制数四位二进制数对应一个十六进制数) )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 例例381.3 1.3 最大公因数与广义

26、欧几里得除法最大公因数与广义欧几里得除法一、最大公因数一、最大公因数 1212,(1.3.12),|(1,2, ),.nkna aan nd aknda aa 设设是是个个整整数数 若若整整数数则则称称 是是 的的一一个个 因因数数定定义义公公 121212,(,).nnna aaa aaa aa 若若不不全全为为零零, ,则则整整数数的的所所有有公公因因数数中中最最大大的的一一个个公公因因数数叫叫做做记记作作最最大大公公因因数数. . 1212,(,)1,nna aaa aa 互互素素特特别别 当当时时 称称或或互互质质. .39 1212120,( ),;(2)|,|.nnnda aad

27、| 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 设设是是两两个个正正整整数数 如如果果则则例例40 ,|,papapa 设设 是是一一个个素素数数, , 为为 整整数数 如如果果则则例例与与4 4互互素素. .:素素数数与与任任一一整整数数有有如如下下关关系系 ,| ,|,dpd ap ap

28、 a 若若则则因因，于于是是与与题题设设矛矛盾盾 ( , ),|,1.p addppdp 证证 设设则则有有因因 是是素素数数 所所以以或或 1,( , )1.dp a 故故必必 从从而而41 (1)|,1,|,1.iid aindain 证证设设则则有有1212,|,|,|nna aaaaa故故的的公公因因数数也也是是的的公公因因数数. . ,|,1,|,1.iidaind ain 反反之之 设设同同样样有有1212|,|,|,nnaaaa aa故故的的公公因因数数也也是是的的公公因因数数. . (2)(1)(2).由由即即得得 1212121212,( ),|,|,|1.3.1|;(2)

29、(,)(|,|,|).nnnnna aana aaaaaa aaaaa 设设是是 个个不不全全为为零零的的整整数数 则则1 1与与的的公公 因因数数相相同同 定定理理42 ,( , )(, )( ,)(|,5|).a ba ba babab 设设是是两两个个整整数数 则则例例有有 1.3.2,().bb = b设设 是是任任一一正正整整数数 则则 0 0, ,定定理理 (0,21)21, ( 156,0)15, (0, ) |.bb 例例 0,(0, ).bbbb 证证 因因任任何何非非零零整整数数都都是是 的的因因数数 而而正正整整数数的的最最大大因因数数为为故故 43.dd ,.db cd

30、d 所所以以 是是的的公公因因数数 从从而而 ,.da bdd 同同理理可可证证, ,是是的的公公因因数数 因因而而故故 18591 1573286, 1573528614 ,73 例例因因(1859,1573)(1573,286)(286,143)143 所所以以 1., ,( , )( ,.).3 3a b ca = bq+cqa b = b c设设是是三三个个不不全全为为零零的的整整数数 如如果果其其中中 是是整整数数 定定理理则则 ( , ), ( , ),a bdb cdd | a d | b 证证 设设则则于于是是|()| ,d aq bd c 44二、广义欧几里得除法二、广义欧几

31、里得除法 111,0nnnnnrr qrr 01,.a bra rb设设是是任任意意两两个个正正整整数数 记记反反复复运运用用欧欧几几里里得得除除法法: : 011221,0,rr qrrr 122332,0,rr qrrr 2111,0,nnnnnnrrqrrr 12110,0.nnnrrrrbnr 因因为为所所以以经经过过有有限限步步骤骤, ,必必存存在在算算法法使使得得（）停停止止45 011223111.3.3,( , )( ,)( ,)( ,)(,)(,)(,0)nnnnnna br rr rr rrrr rrr 于于是是由由定定理理可可知知 1.3.4,( , ).nna bra

32、br 设设是是任任意意两两个个正正整整数数是是广广义义欧欧几几里里得得除除法法中中最最后后一一个个非非零零余余数数 则则 定定理理. 上上述述求求两两个个整整数数的的最最大大公公因因数数的的方方法法叫叫做做也也叫叫广广义义欧欧几几里里得得除除法法, ,辗辗转转相相除除法法做做46 1859,81573,( , ).aba b 计计算算例例设设 18591 1573286157352862862 143143解解 因因( 1859,1573)(1859,1573)143. 所所以以 46480,39423,( , ).aba b 计计算算例例设设9 9解解 最最小小非非负负余余数数法法46480

33、139423705739423570574138 47 522122 1 70571413829194138129191219 29192 121948112192481257 4811257224257122433 22463326331267 263757152 (46480, 39423)1. 所所以以 481nnnrr q 0112,rr qr 1223,rr qr 211,nnnnrrqr 在在广广义义欧欧几几里里得得除除法法中中, ,由由3221,nnnnrrqr 211,nnnnrrqr 1322,nnnnrrrq3122,rrr q 0211qrrr( , )satba b 1

34、232, ,nnrrr rs t逐逐次次消消去去可可找找到到整整数数使使得得49 1859,1573, ,( , )1.0abs tsatba b 设设求求整整数数使使得得 例例 18591 1573286157352862862 143143解解 因因( , )143.s =t =sa + tb = a b 所所以以有有整整数数5 5, ,6 6, ,使使得得 1573528615735(18591 1573143) 于于是是 1573528628618591431 1573 5( 1859)6 1573 50 1.,( , )0,1,2.5,3nnnna bs at ba bnst 设设是

35、是任任意意两两个个正正整整数数, ,则则对对 定定于于这这里里归归为为理理纳纳地地定定义义 1211121100,0,1,10jjjjjjjjsssqsttstttq 2,3,jn jq其其中中是是广广义义欧欧几几里里得得除除法法中中的的不不完完全全商商. . :0,1,2,jjjjjns at brr 只只需需证证明明 对对于于其其中中 是是广广义义欧欧几几里里得得除除 法法中中分分析析: :的的余余数数. . ( , )nnns at bra b ,jn 当当时时 就就有有51 0000001,0,0j =sts at barj 时时, ,由由题题设设以以及及知知结结论论对对于于成成立立.

36、 . j对对 作作数数学学归归纳纳法法. . 1111110,1,1j =sts at bbrj 时时, ,由由题题设设以以及及知知结结论论对对于于成成立立. . 11,jjjjks at br假假设设结结论论对对于于成成立立 即即52 211,kkkkjkrrrq 对对于于有有,由由归归纳纳假假设设 可可得得211211()()kkkkkksqsatqtb 21122111()()kkkkkkkkkrrrqsatbsatb q kks at bjk 结结论论对对于于也也成成立立. . j由由数数学学归归纳纳法法原原理理, ,结结论论对对于于所所有有的的 成成立立. .53 1.3,( , )

37、.5s tsatba b （）由由定定理理及及其其证证明明 可可得得求求算算整整数数得得法法使使的的方方法法. . 010101,1,00,1rarbsstt ,首首先先 令令 100(1)0,rsstt 如如果果则则令令.计计算算结结束束54 01201 11,rqrrq rr（）取取整整否否则则, ,计计算算 211(2)0,rsstt 如如果果则则令令.计计算算结结束束否否则则, ,计计算算 12312 22,rqrrq rr 201 1201 1,ssq sttq t 以以及及 55 11(3)0(3),jjjrjsstt 如如果果则则令令否否则则, ,计计算算 111,jjjjjjj

38、rqrrq rr 211211,jjjjjjjjssqsttqt 以以及及 10,nr 最最后后, ,一一定定有有这这时时, ,令令 ,nnsstt.计计算算结结束束56j a b 11023njq1q2q3qnqjr1jr 1r2r2r3r3r4rnr1nr 1js js2s2s1s3s1ns ns1jt jt1t2t2t3t1nt nt2q 2q :上上述述过过程程可可以以列列表表如如下下|t|s|(,)a b|00r 1r 01s 00t 10s 11t 57 112112111jjjjjjjjjjjjjjjrqrrq rssqstqtrt 1,2,jn 2,3,jn 010101,1,

39、00,1rarbsstt ,其其中中58j123456 737,635, )11(abs tsatba b 设设计计算算整整数数使使得得例例jqjr1jr 1js js1jt jt63573763510635110210011026230111 2311 410106 6 77233252529 29 31156 56 656530193224 |t|s|( , )a b59s193 737( 224) 6351,t 注注所所以以 ，：不不唯唯一一。 1.( ,3.,6)1,1a bs tsatb 存存在在整整数数使使然然理理得得而而，定定 ,|1,( , )1.d | sa + tbda b

40、 = d 所所以以 于于是是因因此此 1.3.5.证证 由由定定理理要要性性即即得得必必 ( , ),| ,| ,d = a bd a d b充充分分性性 设设则则因因sa + tb =1 11.3., , ,5( , )s t dsatbdds t 即即存存在在但但注注：定定理理的的逆逆命命题题不不成成立立，不不一一定定是是的的最最大大公公约约数数。60 ,():(1)| ,| ;(2)| ,| ,.| .1 3.7abdd = a,bd a d be a e be d 设设 ， 是是任任意意两两个个不不全全为为零零的的整整数数是是正正整整数数 则则的的是是 定定理理若若则则充充要要条条件件

41、 ( , ),| ,| .da bd a d b 证证 若若则则显显然然 1.3.5, ,s tsa+ tb = d由由定定理理存存在在整整数数使使得得 | , | ,|,|.e a e be satbe d 于于是是若若则则因因而而 ,(1),da b反反之之 若若成成立立 则则 是是的的公公因因数数; ;61 (2),| ,|,a be ded 则则若若成成立立的的公公因因数数于于是是任任一一 ,da b因因此此是是的的最最大大公公因因数数. .1.3.7(1)(:2)定定理理中中条条件件和和可可以以作作为为最最大大公公因因注注数数的的定定义义. . , (1)(,)( , ).( , )

42、(2)| ,| ,(,).|(,)1.( , ).3 8)1( ,.abmam bma b ma ba bdd a d bd ddaba ba b 设设 ， 是是任任意意两两个个不不全全为为零零的的整整数数. .若若 是是任任一一正正整整数数 则则 若若非非零零整整数数 满满足足则则 特特别别地地, , 定定理理62|.ddm于于是是 ( , ),(,),da bdam bm 证证 ( (1 1) )设设则则存存在在整整satbd ,()()ms amt bmdm 两两端端同同乘乘以以得得 | ,| ,|,|,d a d bdm am dm bm又又因因|,dm d .mddmd = d而而和

43、和都都是是正正整整数数, ,所所以以即即( , )(,).a b mma mb , ,s t数数使使得得63 (,)|ab=ddd (2)| ,|,(1)d a d b当当时时 由由有有 ( , )(|,|)(,)|ababa b =ddddddd ( , ), (,).|aba bddd 因因此此 ,( , ),da b 特特别别地地 取取时时 有有 (,)1.( , )( , )aba ba b 64 11200306,23200306,( , )12.aba b计计算算 例例设设(11,23) 200306200306 (11,23)1, 解解 因因所所以以( , )(11200306,

44、23200306)a b 12,:nna aa个个整整数数的的最最大大公公因因数数的的求求法法 121122233112,0,(,), (,),(,)(,1.3.,9).nnnnnna aanaa addaddada aad 设设是是 个个整整数数, ,且且令令则则 定定理理65 (120 150 210 35). 计计算算最最大大公公因因数数，例例1 13 3 (120,150)(4, 5) 3030解解 因因(30,210)30 (30,35)5 (120 150 210 35)5. 所所以以, ,最最大大公公因因数数 ，最最后后介介绍绍几几个个与与最最大大公公因因数数有有关关的的结结论论

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

46、数是是2 2, a b证证 对对用用广广义义欧欧几几里里得得除除法法, ,得得 1111222123332111,0,0,0,0( , )nnnnnnnnnabqrrbbr qrrbrr qrrbrrqrbrrrarbq 68 11231221112321(21)(21)21(21)(21)21(21)(21)21(21)()21(21)21nnnnnrabrrbrrrrrnrrnrppppp 由由引引理理1 1 1121,nppp 其其中中是是整整数数. . (21, 21)21nrab 由由广广义义欧欧几几里里得得除除法法知知, ,69 ,(21.3.101 21)1( , )aba ba

47、 b 定定理理设设是是两两个个正正整整数数 则则 ,=1. ,=1.2证证 由由引引理理 即即得得结结论论. . ,211.3|.1121baa bb a 设设是是两两个个正正整整数数 则则 定定理理. . , 0abqrrb 证证 设设 121(21)(21), 02121abrrbq 由由引引理理1 1的的证证明明可可得得701212 (2 )(2 )1).rbqbqq 其其中中为为整整数数 |b a. . 21|21210bar 于于是是 0r 711.4 1.4 整除的进一步性质及最小公倍数整除的进一步性质及最小公倍数一、整除的性质一、整除的性质 , ,0,0.( , )(, )( ,

48、 )1.4.1a b cbca cab cb c 设设是是三三个个整整数数, ,且且如如果果1,1,则则 定定理理 ,( , )1.31, ,.16a cs tsatc 反反之之 因因于于是是存存在在定定理理整整数数使使得得（） (, ),( , ).| ,| .dab cdb cdb dc 证证 令令则则有有 |,| .|.dab dcdd于于是是有有从从而而72 ,()()bs abtb cb 两两端端同同乘乘以以得得 |,| ,| ()() ,| .d ab d cd s abtb cd b 由由可可得得即即有有|.d d于于是是.dd 故故 , ,0,|,( , )1,| .a b c

49、cc aba cc b 设设是是三三个个整整数数 且且如如果果 则则 推推论论1.4.1|(, )( , ),cab cb c 证证 由由题题设设条条件件及及定定理理, ,有有| .c b从从而而73 ,|,| .1.4.2pp abp ap b设设 是是素素数数 若若则则或或定定理理 |,1.4.1| .p abp b又又因因由由定定理理之之推推论论有有 |,( , )1.pp ap a 证证 因因 是是素素数数, ,所所以以若若则则 , ,( , )1,( , )1,1(, )1.4.3a b ca cb cab c 设设 定定是是整整数数 若若理理则则1.4.1,(, )( , )1.a

50、b cb c证证 由由题题设设及及定定理理有有1212,(, )1,1,(, )1.nina aa ca cina aa c 推推广广: :设设是是整整数数 如如果果则则74 1212,|,|.nnka aapp a aapa 设设是是整整数数是是素素 推推论论数数. .如如果果则则某某个个 |,(, )1,1iippaapin 证证( (反反证证法法) ) 因因 是是素素数数, ,所所以以若若则则12(, )1.na aap 于于是是有有 12|.np a aa与与题题设设 矛矛盾盾75二、最小公倍数二、最小公倍数 1212121212,|,|,|,.1.4.1nnnnna aanam am

51、amma aaa aaa aa设设是是 个个整整数数 若若则则 叫叫做做的的一一个个. . 的的所所有有公公倍倍数数中中最最小小正正整整数数叫叫做做记记作作 公公倍倍数数最最 公公数数 定定小小倍倍义义 12,(1)|, 1;(2)|, 1,|.niima aaaminaminm m 若若则则:易易知知76 ,(1)|, |,1|;(2) , .4.4a ba m b mab ma bab 设设是是两两个个互互素素的的正正整整数数 则则定定理理若若则则.mabt 于于是是|,a mmak 证证 ( (1 1) ) 因因, ,则则|,|,b mb ak又又即即( , )1,| ,a bb k 而

52、而所所以以,kbt 由由此此可可得得|.ab m故故 (2),|,|aba ba mb m显显然然是是的的公公倍倍数数. .又又若若, , (1)|.ab m由由,aba b所所以以是是的的最最小小公公倍倍数数 故故 , .a bab 77123123, aaa aaa 于于是是 121212(,)1,1.4.4,.a aa aa a 证证 因因 由由定定理理 12,na aan设设是是 个个两两两两互互素素的的正正整整 推推数数 广广即即 1212(,)1,1,.ijnna ai jnija aaa aa , ,则则 1323123(,)(,)1,1.3.3 (,)1,a aa aa a a

53、 又又由由定定理理, ,123123,.a a aa a a ,如如此此继继续续 可可得得 1212,.nna aaa aa 78 ,(1) , . , ( , )1.( , )(2)|, |, , |.4.5.a baba ba b a baba ba m b ma bm设设是是两两个个正正整整数数即即若若定定则则则则理理, ,a b对对于于一一般般的的正正整整数数有有 12.( , )( , )abkka ba b ,ma b证证 ( (1 1) )设设是是的的一一个个公公倍倍数数, ,那那么么存存在在整整1212,k kmak mbk 数数使使得得因因此此12,akbk 79(,)1.(

54、 , ) ( , )aba ba b 由由于于 1|,( , )bka b所所以以有有1,.( , )bkt ta b 即即有有为为某某个个整整数数1,( , )abmakta b于于是是,( , )abtta ba b另另一一方方面面, ,对对任任意意的的整整数数 , ,显显然然是是的的公公,( , )aba bmmta b 所所以以的的任任一一公公倍倍数数可可表表成成的的形形式式. .倍倍数数. .801,t 当当时时 得得到到最最小小公公倍倍数数 , ( , )aba ba b 任任意意两两个个正正整整数数的的乘乘积积等等于于这这两两个个数数的的最最小小公公倍倍数数与与最最大大公公因因数

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

56、.,6nnnnnna aana ammammama aam 设设是是 个个整整数数 令令 定定理理, ,则则 = =. . , , .1p qp qpq 设设是是两两个个不不同同的的素素数数 则则例例82 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. 故故 83 1212,1.1,.7,|.nnma aaa aam若若是是整整数数的的公公倍倍数数 则则 定定理理

57、n由由数数学学归归纳纳法法原原理理, ,命命题题对对所所有有的的 成成立立. .n证证 对对 作作数数学学归归纳纳法法. .21.4.5n 时时, ,由由定定理理, ,命命题题成成立立. .1(3nn假假设设) )时时, ,命命题题成成立立. .即即1121,|nnma aam 1|,nnmm 对对于于 , ,由由归归纳纳假假设设, ,有有|,1.4.5,nam又又由由定定理理1,|.nnmam 11212,|.nnnnmaa aaa aam 而而, ,故故841.5 1.5 素数素数 算术基本定理算术基本定理 121212121.5.1(1),(), 1ssittjiin nnp ppppp

58、pnq qqqqqqst pqis 任任一一整整数数都都可可以以表表成成素素数数的的乘乘积积. .且且在在不不考考虑虑乘乘积积次次序序的的情情况况下下, ,表表达达式式是是的的. .算算术术基基本本唯唯即即其其中中 是是素素数数 且且若若其其中中 是是素素定定理理 一一 定定理理数数. . 则则 1212,(1)ssnp ppppp 证证 用用数数学学归归纳纳法法证证明明表表达达式式 85n假假设设对对于于小小于于 的的正正整整数数, ,结结论论成成立立. .n对对于于正正整整数数 2,n 时时 结结论论显显然然成成立立. .,(1).n若若 是是素素数数 则则式式显显然然成成立立 ,1,1n

59、b cnbcbncn 若若 是是合合数数, ,则则存存在在正正整整数数, ,使使得得 1212,uusbpppcppp 由由归归纳纳假假设设 有有 1212uusnbcpppppp 于于是是 86,1,(1).n 由由归归纳纳法法原原理理 对对于于所所有有的的整整数数式式成成立立,(1).ip适适当当改改变变的的次次序序 即即得得式式.再再证证表表达达式式的的一一性性唯唯 11,.jjp qpq 但但都都是是素素数数 所所以以 1212,ttnq qqqqq假假设设还还有有 ,jq其其中中是是素素数数 则则 1212(2)stp ppq qq 112|,tpq qq因因此此11,|,jjpqp

60、q因因 是是素素数数 故故存存在在使使得得871,kkpqp 同同理理, ,存存在在使使得得11.pq 即即有有 于于是是111kjppqpq 1(2),p代代入入消消去去得得22stppqq , 1iistpqis 重重复复上上述述过过程程 最最后后可可得得88121212,0,1,2,5(12). .ssisijnnpppispppppijn 任任一一大大于于1 1的的整整数数 能能够够唯唯一一地地表表示示成成 ( (* *) )其其中中为为素素数数, , 分分解解式式( (* *) )叫叫做做定定标标准准分分的的理理解解式式. . 1212,1,2,0kiknnpppik 有有时时为为了