信息保障与安全课件：第2章 不定方程与同余.ppt

1、2022-1-20计算机科学与技术学院1信息安全数学基础第2章 不定方程与同余2022-1-20计算机科学与技术学院2主要内容主要内容不定方程同余同余的基本概念与性质剩余类与完全剩余系简化剩余系与欧拉函数欧拉定理、费马小定理模重复平方计算法一、不定方程一次不定方程：2022-1-20计算机科学与技术学院3我们关心的：1. 方程何时有整数解？2. 如果有整数解，有多少解，解又是什么形式？2022-1-20计算机科学与技术学院42022-1-20计算机科学与技术学院52022-1-20计算机科学与技术学院62022-1-20计算机科学与技术学院72022-1-20计算机科学与技术学院8练习： 1.

2、 求10 x-7y=17的解 2. 求18x+24y=9的解1. x=1-7t；y=-1-10t2. 无解2022-1-20计算机科学与技术学院92022-1-20计算机科学与技术学院10求n元一次方程解的方法：2022-1-20计算机科学与技术学院11练习：求15x+10y+6z=61的解2022-1-20计算机科学与技术学院12解：x=5+2t+6sy=-5-3t-6sz=6-5s2022-1-20计算机科学与技术学院132022-1-20计算机科学与技术学院142022-1-20计算机科学与技术学院152022-1-20计算机科学与技术学院162022-1-20计算机科学与技术学院172

3、022-1-20计算机科学与技术学院18方程方程x2 y2 = z2 x2 y2 = z2 （1）若(x, y, z)是方程(1)的解，则对于任何整数k，(kx, ky, kz)也是方程(1)的解若(x, y) = k，则kz，(x, y, z) = k 2022-1-20计算机科学与技术学院19方程方程x2 y2 = z2 满足xyz=0的解称为显然解显然解；否则，称为非显然解非显然解容易看出全体显然解是： 0，a， a； a，0， a a 0如果x，y，z是方程的非显然解，则对于任意的k， kx， ky， kz也是方程的非显然解；且对于x，y，z的任意正公约数d， x/d， y/d， z/

4、d也是方程的非显然解2022-1-20计算机科学与技术学院20的解的解因此我们只需求满足下式的解，称为本原解本原解： x0,y0,z0,(x,y,z)=1 (2)2022-1-20计算机科学与技术学院212022-1-20计算机科学与技术学院222022-1-20计算机科学与技术学院232022-1-20计算机科学与技术学院242022-1-20计算机科学与技术学院252022-1-20计算机科学与技术学院262022-1-20计算机科学与技术学院272022-1-20计算机科学与技术学院28费马大定理n2是整数，则方程是整数，则方程xn+yn=zn没有满足没有满足xyz0的整数解的整数解 英

5、国数学家怀尔斯于1995年证明2022-1-20计算机科学与技术学院29本部分重点内容：求解一次线性不定方程练习：5967部分证明题答案在课件中2022-1-20计算机科学与技术学院30同余的概念和基本性质同余的概念和基本性质2022-1-20计算机科学与技术学院3132 2.1 2.1 同余的概念及其基本性质同余的概念及其基本性质基本基本概念概念,|, , (mod), (mod ).ma bm ababmabmmabm 给给定定一一个个正正整整数数如如果果对对于于整整数数有有则则叫叫记记作作否否则则 叫叫做做模模定定义义作作不不同同余余 记记1 1 ， 做做模模 同同余余, , 7 | 2

6、91,291 (mod17).因因 所所以以 例例 7 | 235,235 (mod7). 因因 所所以以 同同余余的的概概念念经经常常出出现现在在日日常常生生活活中中。例例如如：时时针针是是模模1212或或2424小小时时，分分针针和和秒秒针针是是模模606033二、基本定理及性质二、基本定理及性质 ,(mod),.1ma babmkabkm 设设 是是一一个个正正整整数数, ,是是两两个个整整 数数, ,则则的的是是存存在在整整数数使使 定定理理要要条条件件得得充充 (mod)|abmm ab证证 .abkmkabkm 存存在在整整数数 使使得得 678 83,673 (mod8).2因因

7、所所以以例例34()(,(1) , (mod); (2) (mod), (mod); (3) (mod), (mod), (mod) 2 )() ma aamabmbamabm bcmacm 自自反反性性对对称称模模 同同余余是是等等价价关关系系 即即对对 任任一一整整数数性性 若若则则定定理理则则若若传传递递性性 (1)|0,(mod).m aaaam证证 因因所所以以 (2)(mod),|,|,abmm abm ba若若则则有有于于是是 (mod).bam (3)(mod),(mod),|,|,abm bcmm ab m bc若若则则 |()(),(mod).mabbcacacm于于是是故

8、故35,a bma bm整整数数模模 同同余余的的 是是被被定定理理3 3除除的的余余充充要要条条件件 数数相相同同. . , 0, 0aqmrrmbq mrrm证证 设设 ()()abqq mrr则则 |.m abm rr于于是是|,rrm但但0 0|0,.m rrrrrr所所以以 即即 395 74, 253 74,4因因 例例 3925 (mod7). 所所以以 36:整整数数间间的的同同余余关关系系还还有有以以下下性性质质1212112212121212, (mod), (mod),(i) (mod) (ii)4 (mod)ma ab babmabmaabbma ab bm 设设是是一

9、一个个正正整整数数，是是整整数数. .若若 则则 定定理理同余式可逐项相同余式可逐项相加、减、乘加、减、乘, (mod), (mod)abmakbkm 特特别别地地 若若则则111222+ (mod), ,abk mmabk m1122 (mod), (mod),abmabm证证 因因由由定定理理1 13711 21212212122112()()aabbkkma ab bk bk bk k m m于于是是 12122112,1kkk bk bk k m因因都都是是整整数数 所所以以由由定定理理 有有11 212212(mod)(mod)aabbma ab bm 39 224 1 (mod7)

10、,8584 (mod7)即即 394 (mod7)221 (mod7)5,因因 ，例例所所以以 392241 (mod7),615 (mod7)即即38 2003200358,26?年年 月月 日日是是星星期期五五 问问第第天天是是星星期期几几例例1 44(mod7) 2322(mod7),24 (mod7),281(mod7),解解 因因 2003667 32,又又 所所以以2003667 3 23667222(2 )2 20032故故第第天天是是星星期期二二.(.(星星期期五五加加4 4天天) )390101 (mod), (mod),0,1,2, , (mod)iikkkkxym abm

11、ikaa xa xbb yb ym 若若 定定理理 则则5 5 0101 (mod)kkkkaa xa xbb yb ym从从而而 (mod), (mod), 0iixymxymik 证证 设设 于于是是有有(mod), 0, iiabmik又又 所所以以有有(mod), 0iiiia xb ymik4011101010101010, 0103|6 3|,9|9| .kkkkikkkknnaaaaanaaanaaa 设设整整数数 有有十十进进制制表表示示式式: :则则 而而 定定理理 1110110101010(mod3)kkkkkkaaaaaaaa 101(mod3),(mod3),11(m

12、od3),iiiaa证证 因因5由由定定理理 有有0,ik41 1100 (mod3)kkaaaa 所所以以 11103|1010100 (mod3)kkkknaaaa 1103|kkaaaa 10101 (mod9),9|9|kknaaa 因因所所以以同同理理可可证证 3| 36, 9| 36,3| 5874192, 9| 5874192.所所以以 5874192,5874192376n 设设因因 例例4210213010001000,01000,7(11,13)7(11,13)()()() 17 kkikiiinnaaaanaaaaa 0 0设设 有有10001000进进制制表表示示式式则

13、则或或或或整整除除或或或或整整除除 定定理理 352461000100010001 (mod7),1000100010001 (mod7), 即即 10001 (mod7), 证证 因因 所所以以 1000( 1) (mod7), 0.iiik 431110( 1)( 1)( 1)kkkkaaaa 于于是是1110100010001000kkkkaaaa 213()() (mod7)aaaa0 0 10001 (mod11),10001 (mod13),1113mm 因因 所所以以结结论论对对于于或或也也成成立立. .44 637693637 10008693,n 例例设设有有 1693637

14、56aa0 0 7 | 56,11 | 56, 13 | 56,因因而而故故 7 | 637693,11 | 637693, 13 | 637693.但但45 (mod), ( ,)1, 8(mod)madbdmd mabm 设设是是一一个个正正整整数数, ,如如果果则则 定定理理 ( ,)1,|,d mm ab因因 所所以以故故 (mod),|,adbdmm adbd证证 若若 则则即即| ()m d ab (mod)abm m上上面面几几个个性性质质, ,其其模模不不发发生生变变化化, ,属属于于基基本本性性质质. .46以以下下是是模模发发生生变变化化的的几几个个性性质质. . (mod

15、),0, (m d)9omabm kakbkmk 设设是是正正整整数数, ,则则 定定理理 (mod)akbkmk (mod)|abmm ab证证 由由|()mkab kakbk47 (mod), (mod).10mabmda, bmabmddd 设设是是正正整整数数, ,如如果果是是及及 的的任任一一公公因因数数 则则 定定理理 , ,a b md dd因因都都是是整整数数 故故 (mod),abmk 证证 因因所所以以存存在在整整数数使使得得abmk,abmkddd于于是是 (mod)abmddd 48 (mod), 011, (mod ).mabm d | m, dabd 设设是是正正整

16、整数数, ,如如果果则则 定定理理 (mod )abd 故故 (mod),|.abmm ab证证 因因所所以以 |,|.d md ab 又又因因 于于是是 19050 (mod70), 9 9因因例例 195 (mod7), 19050 (mod7)所所以以 491212, (mod),1,2, , (mod, .1)2kikmmmabmikabmmm 设设是是正正整整数数, ,且且则则 定定理理 12(mod,)kabm mm 故故 ,(mod),1,2,iabmik证证 因因则则 |,1,2,imab ik12,|km mmab 于于是是 501212, (mod),1,2, , (mod

17、).kikm mmabmikabm mm 设设是是两两两两互互素素的的正正整整数数且且 则则 推推 论论 ,(mod),(mod )(mod10).p qabpabqabpq 设设是是不不同同的的素素数数 如如果果有有则则 例例 (mod , ),abp q 证证 由由题题设设及及定定理理12,12,有有 ( , )1, , .p qp qpq又又因因所所以以故故 (mod)abpq 51 (mod), ( ,)( ,).3 .1mabm a mb mdma, bda, b 设设是是正正整整数数, ,则则 因因而而若若 能能整整除除及及二二者者之之一一 则则 必必能能 定定整整除除中中的的个个

18、理理另另一一, , (mod),abmkabmk 证证 因因则则存存在在整整数数使使得得 | ,| ;| ,| .h a h mh bh b h mh a上上式式表表明明: :由由由由 ,a mb m即即与与有有相相同同的的公公因因数数 从从而而 ( ,)( ,)a mb m 52 , ,0,1 (mod),0,1 (mod)11aam n anmnppm 设设都都是是正正整整数数 如如果果则则存存在在 的的一一个个素素因因数数使使得得例例即即有有 (),np证证若若存存在在 的的一一个个法法素素因因数数反反证证使使得得0(mod)apm |amp则则. .| ,|,|,aaap npnm n

19、又又因因有有于于是是0(mod),.anm 与与题题设设矛矛盾盾53 0 (mod).apm ,np又又如如果果对对 的的每每个个素素因因数数都都有有 1 (mod)apm 41(mod),anm 则则由由定定理理 有有与与题题设设矛矛盾盾. .,np于于是是存存在在 的的一一个个素素因因数数使使得得p又又由由前前面面证证明明可可知知, ,这这个个 也也满满足足 1 (mod).apm ,0(mod).anppm 这这说说明明对对 的的所所有有素素因因数数都都有有54是是大大自自然然的的循循环环现现象象, ,研研究究同同优优点点 余余的的在在于于: :化化同同无无余余”限限注注: : “为为有

20、有限限. . 运运算算后后把把同同余余式式译译为为等等式式又又将将等等式式译译为为同同余余式式. .证证明明同同余余式式的的一一般般方方法法( (基基本本的的方方法法):):其其理理论论根根据据是是: : (mod)|abmm ab 55三、验算整数计算结果的方法（弃九法）三、验算整数计算结果的方法（弃九法） 1101101101010(,010)1010(,010)1010(,010)nnnninnnninnnnia aZab bZbabccc cZc 设设 a=aaa=aab=b= b b原原理理b bc c000)(mod9),nnnijkijkabc 如如果果(则则所所求求的的结结果果

21、是是错错误误的的。怎怎样样检检验验错错误误：56110( )nnnnf xa xaxaZ X 设设事事实实上上：101(mod9),(10)(1)(mod9)ff 0(mod9)niiaa 即即0(mod9)njibb 同同理理可可证证：0(mod9)nkkbc a a根根据据同同余余的的性性质质：57但但若若故故所所求求计计算算结结果果是是错错误误的的。00)()(mod9)nnijijbab a a（000)()(mod9)nmlijkijkabc （2368 846200332823145 926532910 93995例例：1 1）用用弃弃九九法法验验算算下下列列等等式式：；）在在乘乘

22、法法？有有位位数数码码遗遗漏漏，用用弃弃九九法法找找出出遗遗漏漏数数码码。重点内容同余的性质：1. 同余是一种等价关系2. 同余可进行加、减和乘运算3. 同余可进行包括模在内的乘、除（公因子）运算4. 同余关于模的因子也同余5. 同余关于最小公倍数也同余6. 同余的整数与模的最大公因子相等2022-1-20计算机科学与技术学院58592.2 2.2 剩余类及完全剩余系剩余类及完全剩余系一、基本概念一、基本概念(),m 把把同同余余 关关于于模模的的整整数数放放在在一一起起 可可以以把把整整数数分分类类. ., | (mod),amaCc acm cZ设设是是一一个个正正整整数数 对对任任意意整

23、整数数令令,.aaaCC 因因所所以以60,(i) 1(ii) (mod);(iii) (mod);1 rababmCrmCCabmCCabm 设设 是是一一个个正正整整数数 则则任任一一整整数数必必包包含含在在一一个个中中 定定理理 ,0; ,0; (mod),.rramaC因因此此 于于是是 (i),0aamqrrm证证欧欧几几 设设 为为任任一一整整里里由由得得除除法法数数有有 (ii),ababCCaCC设设则则 (mod).abm 反反之之, ,设设,acC 对对任任意意则则 (mod).abm 于于是是61.abCC 与与假假设设矛矛盾盾 故故 (mod)acm (mod),bcm

24、 于于是是,bcC 所所以以.abCC 故故.baCC 同同理理可可证证.abCC 从从而而 (iii)(ii)由由即即得得必必要要性性. . (mod).,ababmCC ( (反反证证法法) ) 设设若若下下证证充充分分性性. .,abcCcC则则有有于于是是有有 (mod)(mod)acmbcm及及 (mod),abm 从从而而62011011 |, , , ,1 ammCc ac cZmar rrmr rrm 叫叫做做模模的的的的一一个个剩剩余余类类中中的的任任一一数数叫叫做做该该类类的的或或若若是是 定定义义剩剩余余类类. .剩剩余余代代表表元元个个整整数数 并并且且其其中中任任何何

25、两两个个数数都都不不在在同同一一个个剩剩余余类类里里 则则叫叫做做模模. .完完全全. .一一个个系系的的剩剩余余 0111.,.2:.mmmCCCmmmm 模模 的的剩剩余余类类有有个个 在在同同一一剩剩余余类类中中的的数数互互相相同同余余, ,不不在在同同一一剩剩余余 类类的的数数互互不不同同余余. .模模 的的完完全全剩剩余余系系恰恰有有个个整整数数. .个个注注连连续续的的整整数数也也是是模模 的的完完全全剩剩余余系系. .63 ,1, 1,0,1,1222 1, 1,0,1,1,222mmmmmmmm例例如如为为偶偶数数时时或或都都是是模模 的的完完全全剩剩余余系系. . 11 ,

26、1,0,1,22mmmm为为奇奇数数时时也也是是模模 的的完完全全剩剩余余系系. .64 10,1011|0amaCak kZm 设设对对任任意意整整数数集集合合是是 例例模模的的剩剩余余类类. .0100|20, 10,0,10,20,CkkZ1101|19, 9,1,11,21,CkkZ9109|11, 1,9,19,29,CkkZ0,1,2,3,4,5,6,7,8,910是是模模的的一一个个完完全全剩剩余余系系. .1,2,3,4,5,6,7,8,9,1010是是模模的的一一个个完完全全剩剩余余系系. .65二、有关完全剩余系的几个定理二、有关完全剩余系的几个定理 011,(mod),

27、,0,1,.21mijmmr rrmrrmij i jm 设设是是一一个个正正整整数数 则则个个整整数数为为模模 的的一一个个完完全全剩剩余余系系的的充充要要条条件件是是 定定理理011,mr rrm 证证 是是模模 的的一一个个完完全全剩剩余余系系,()ijr r ij 它它们们中中任任意意两两个个数数不不在在同同一一剩剩余余类类 (mod), ,0,1,1.ijrrm ij i jm 66mm 设设 是是一一个个正正整整数数, ,则则常常用用的的几几个个模模 的的完完 例例2 2全全剩剩余余系系: : 0, 1, 2, , 1m 最最小小非非负负完完全全剩剩 余余系系( (1 1) ) 1

28、, 2, , 1, mm 最最小小正正完完全全剩剩余余系系( (2 2) ) (1), (2), , 1, 0mm ( (3 3 最最大大非非正正完完) )全全剩剩余余系系 , (1), , 2, 1mm 最最大大负负完完余余系系4 4) )全全剩剩( (67 , 1, , 1, 0, 1, , 1222 1, , 1, 0, 1, , 1, ,222mmmmmmm为为偶偶数数时时, ,为为或或 ,11 , , 1, 0, 1, , 22mmm为为奇奇数数时时 为为(5) 绝绝对对值值最最小小完完全全剩剩余余系系68(, ,)1ambxmaxbmm 设设 是是正正整整数数, ,是是任任意意整整

29、数数, ,若若 遍遍 历历模模 的的一一个个完完全全剩剩余余系系, ,则则也也遍遍历历模模的的一一个个完完全全定定理理3 3剩剩余余系系. .01-1011, mmaaamaa + baa + baa+ bm 即即: :若若是是模模 的的完完全全剩剩余余系系, ,则则， ，也也是是模模 的的完完全全剩剩余余系系. . (mod,):) (.ijaabaabmij 分分只只需需明明析析证证即即可可 ,( ,)1.a m 可可用用反反证证法法 利利用用69 (mod),()ijaamij(),ijaaij 证证 若若存存在在 和和使使得得 (mod),()ijaabaabmij| ().ijm a

30、 aa 则则( ,)1,|,ija mm aa因因所所以以于于是是01-1,maaam这这与与是是模模 的的完完全全剩剩余余系系的的假假设设矛矛盾盾. .011 maa + baa + baa+ b ， ，故故m是是模模 的的完完全全剩剩余余系系. .70 10,7,5.:310mabx设设当当 遍遍历历模模的的完完全全 例例剩剩余余系系 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,510 x 时时 形形如如7 7的的个个整整数数10也也构构成成模模的的完完全全剩剩余余系系. . 5, 12, 19, 26, 33, 40, 47, 54, 61, 6871 12, ,( ,)1

31、,(1),1,2,mixxxma b mZa mxbmm mmm若若是是 的的完完全全剩剩余余系系，且且则则a a除除以以 的的余余数数之之和和1 1为为其其中中2 2 练练习习：7212121221122112,0(,0,)1 mmxxm mm xm mm xm m 若若而而分分别别遍遍 定定理理历历模模的的完完全全剩剩余余系系 则则遍遍历历模模的的完完全全剩剩余余系系. . 4 4 , ,12m m所所以以只只需需证证明明这这个个121221,xxm mm x 证证 因因分分别别遍遍历历个个整整数数时时1212m xm m遍遍历历个个整整数数. .12.m m整整数数对对模模两两两两不不同

32、同余余即即可可1212,xxyy若若有有整整数数, ,使使得得 2112211212(mod)m xm xm ym ym m73112|,mm m则则因因所所以以 211221121(mod)m xm xm ym ym 21211(mod)m xm ym 所所以以 )1211|(mmxy 于于是是 12111(,)1,|.m mmxy但但因因 所所以以 111(mod),xym 于于是是 222(mod)xym 同同理理 故故定定理理成成立立. .74 , ,(4mod ), 0, 0p qnpqcx yqxpycnxpyq 设设是是两两个个不不同同的的素素数数则则对对任任意意的的整整数数存存

33、在在唯唯一一的的一一对对整整数数满满足足 例例 ,( , )1.p qp q 证证 因因是是两两个个不不同同的的素素数数 所所以以 4,x yp q由由定定理理 及及其其证证明明 知知分分别别遍遍历历的的完完全全剩剩余余系系, c因因此此对对于于整整数数, x y存存在在唯唯一一的的一一对对整整数数满满足足 (mod ), 0, 0qxpycnxpyq,qxpynpq时时遍遍历历的的完完全全剩剩余余系系. .752.3 2.3 简化剩余系与欧拉函数简化剩余系与欧拉函数一、欧拉一、欧拉(Euler)函数函数0,1,2,1().1)mmmmmEuler 设设是是一一个个正正整整数数, ,则则个个整

34、整数数中中与与互互素素的的整整数数的的个个数数, ,记记作作通通常常 定定义义称称为为欧欧拉拉函函数数. . ( ( )()0,1,2,1Eulerxmmm 定定义义在在正正整整数数上上的的函函数数 即即: :欧欧拉拉函函数数是是, ,的的值值等等于于中中与与互互素素的的数数的的个个数数. .()() (10)4,(7)6例例1 1 欧拉（Leonhard Euler，1707-1783）1707年出生在瑞士的巴塞尔城。18世纪最优秀的数学家，也是历史上最伟大的数学家之一，被称为“分析的化身”2022-1-20计算机科学与技术学院76欧拉（Leonhard Euler，1707-1783） 从

35、小就特别喜欢数学，不满10岁就开始自学代数学 13岁进巴塞尔大学读书，在当时是个奇迹，曾轰动数学界；得到最有名的数学家微积分权威约翰伯努利（Johann Bernoulli，1667-1748）的精心指导 两年后，获得学士学位; 次年，又获得哲学硕士学位。1725年，欧拉开始了他的数学生涯 1727-5-17来到彼得堡。1733年年仅26岁的欧拉担任了彼得堡科学院教授。1735年解决了一个天文学的难题，该问题经几个著名数学家几个月努力才得到解决，而欧拉却用自己的方法三天便完成了. 过度工作使他得了眼病，28岁右眼失明，1766年左眼失明 完全失明后，仍然凭着记忆和心算进行研究直到逝世，达17年

36、之久（欧拉的两个学生把一个复杂的收敛级数的17项加起来，算到第50位数字，两人相差一个单位，欧拉为了确定究竟谁对，用心算进行全部运算，最后把错误找了出来）2022-1-20计算机科学与技术学院77 据统计他共写下了856篇论文，专著32部，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%，彼得堡科学院为整理他的著作，足足忙碌了47年 费马大定理：费马在提出这一猜想的同时，在纸边写了一句话宣称：“我已找到了一个奇妙的证明，但书边空白太窄，写不下。”于是费马的证明已成千古之谜。此后经过300年，直到1993年费马大定理才被英国数学家最终

37、解决。整个18世纪，数学家们都想解决这个猜想，但只有欧拉作出了唯一的成果，证明了n=3的情况，成为费马大定理研究的第一个突破 歌德巴赫猜想也是在他与歌德巴赫的通信中提出来的 初等数论：欧拉函数、二次互反律2022-1-20计算机科学与技术学院78歌德巴赫猜想 分为两个猜想：1.每个不小于6的偶数都可以表示为两个奇素数之和；2.每个不小于9的奇数都可以表示为三个奇素数之和每一个数是若干素数之积。把命题每一个大偶数可以表示成为一个素因子个每一个大偶数可以表示成为一个素因子个数不超过数不超过a个的数与另一个素因子不超过个的数与另一个素因子不超过b个的数之和个的数之和记作a+b“ 1920年，挪威的布

38、朗证明9 + 9 1924年，德国的拉特马赫证明7 + 7 1932年，英国的埃斯特曼证明6 + 6 1937年，意大利的蕾西先后证明5 + 7,4 + 9,3 + 15和2 + 366 1938年，苏联的布赫夕太勃证明5 + 5 1940年，苏联的布赫夕太勃证明4 + 4 1948年，匈牙利的瑞尼证明了1+ c，其中c是一很大的自然数 1956年，中国的王元中国的王元证明了3 + 4 1957年，中国的王元中国的王元先后证明了 3 + 3和2 + 3 1962年，中国的潘承洞中国的潘承洞和苏联的巴尔巴恩证明了1 + 5， 王元王元证明1 + 4 1965年，苏联的布赫夕太勃和小维诺格拉多夫，

39、及意大利的朋比利证明1 + 3 1966年，中国的陈景润中国的陈景润证明了1 + 22022-1-20计算机科学与技术学院7980二、简化剩余系二、简化剩余系2mmm如如果果模模 的的剩剩余余类类里里面面的的数数与与互互素素, ,就就把把这这个个类类叫叫做做一一个个与与模模互互剩剩余余类类素素的的.(.(又又称称 定定义义) )简简化化剩剩余余类类 mmm设设是是一一个个正正整整数数 在在模模 的的所所有有不不同同简简化化剩剩余余类类中中, ,从从每每个个类类任任取取一一个个数数组组成成的的整整数数的的集集合合, ,叫叫做做模模简简化化剩剩余余系系一一个个. .定定义义的的 3 3 , , 0

40、19137910,101,3,7,910mCCCC CCC 模模的的剩剩余余类类中中, ,是是例例2 2模模的的简简化化剩剩余余类类. .是是模模的的一一个个简简化化剩剩余余系系. .811212,)1( ,)1.r rmr mr m 设设是是同同一一模模 剩剩余余类类的的两两 个个剩剩余余, ,则则( ,( , 定定理理1 112( ,)1( ,)1r mr m故故 12(mod)rrm 证证 由由题题设设 , ,于于是是有有12( ,)( ,).r mr m 因因而而 12rrkmmm此此定定理理说说明明: :模模 的的简简化化剩剩余余类类中中的的数数都都与与互互素素. .820,1,2,

41、1mmmm 为为此此, ,只只需需在在模模 的的最最小小非非负负完完全全剩剩余余系系里里找找出出与与互互素素的的所所有有整整数数, ,则则这这些些整整数数的的全全体体就就构构成成模模 的的一一个个简简化化剩剩余余系系. . mm 由由欧欧拉拉函函数数的的定定义义知知, ,模模 的的简简化化剩剩余余系系里里共共含含()()个个数数. . 1, 7, 11, 13, 17, 19, 23, 29303 是是模模的的简简化化剩剩 余余系系. (30. (30 例例)=8.)=8. ,1, 2, 3,( )411ppmppp 当当为为素素数数时时是是模模的的简简化化剩剩余余系系. .所所以以 例例.

42、.83:几几类类特特殊殊的的简简化化剩剩余余系系 (1)0,1,2,1mmmmm 个个整整数数中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系, ,叫叫最最小小非非负负简简化化做做模模 的的剩剩余余系系. . 5m设设是是一一例例个个正正整整数数, ,则则 (2)1,2,1,mmmmmm 个个整整数数中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系, ,最最小小正正简简化化叫叫做做模模 的的剩剩余余系系. . (3)1), 1,0mmmmm个个整整数数-(-(中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化

43、化剩剩余余系系, ,最最大大非非正正简简化化叫叫做做模模 的的剩剩余余系系. .84 , (5),1, 1,0,1,12221, 1,0,1,1,222mmmmmmmmmmm当当 为为偶偶数数时时个个整整数数-或或个个整整数数 - -中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系. . (4), (1), 1mmmmmm个个整整数数-中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系最最大大负负简简化化, ,叫叫做做模模 的的剩剩余余系系. .85, 11, 1,0,1,22mmmmmm 当当 为为奇奇数数时时个个整整数数-

44、-中中与与互互素素的的整整数数全全体体组组成成模模 的的一一个个简简化化剩剩余余系系. .m 这这两两个个简简化化剩剩余余系系统统称称为为绝绝对对值值最最小小模模 的的简简化化剩剩余余系系. .86三、有关简化剩余系的定理三、有关简化剩余系的定理12() ( ,)1, 1,2,3, (), (mod) (),iijmmr mimrrmijr rrm 设设 是是一一个个正正整整数数, ,且且则则是是模模的的一一个个简简化化剩剩余余系系. . 定定理理 2 2()mm 证证 因因模模 的的简简化化剩剩余余系系恰恰含含个个整整数数. .12() (mod) (),()ijmrrmijr rrmm 又

45、又因因所所以以是是模模的的不不同同剩剩余余系系中中的的个个数数. .,()mmm 由由题题设设 这这个个数数都都与与互互素素. .故故它它们们组组成成模模 的的一一个个简简化化剩剩余余系系. .87( ,)1mxmaxma m 设设 是是一一个个正正整整数数,若若 遍遍历历模模 定定的的简简化化剩剩余余系系, ,则则也也遍遍历历模模 的的简简理理3 3化化剩剩余余系系. .( ,)1,( ,)1,(,)1.a mx max m因因所所以以有有12()12()(),(),mmxmxmxxxaxmax axax 证证 当当 遍遍历历模模 的的简简化化剩剩余余系系时时, , 遍遍历历个个整整数数,

46、,从从而而遍遍历历个个整整数数. . (mod), ().ijaxaxmij 所所以以只只需需证证明明 即即可可 ,(mod) (),ijaxaxmij若若( ,)1,a m 则则因因88这这与与题题设设矛矛盾盾. . (mod),(),ijxxmij所所以以axm故故遍遍历历模模 的的简简化化剩剩余余系系. . 7 17(mod30),7 74919(mod30),7 117717(mod30),7 13911(mod30),7 1711929(mod30), 7 1913313(mod30),7 2316111(mod30), 7 2920323(mod30) 30,7,1,7,11,13

47、,17,19,23,2930,(7,30)1,6ma 设设模模已已知知是是模模的的 例例简简化化剩剩余余系系有有 7, 49, 77, 91, 119, 133, 161, 20330 所所以以是是模模的的简简化化剩剩余余系系. .2022-1-20计算机科学与技术学院8990( ,)1,1, 1 (mod)ma maamaam 设设 定定是是一一个个正正整整数数,则则存存在在整整数数得得理理使使4 4( ,)1,a mxm 因因当当 遍遍历历模模 的的() 存存在在证证性性证证明明一一,ax一一个个最最小小正正简简化化剩剩余余系系时时也也遍遍历历模模的的一一个个简简化化剩剩余余系系. .,1

48、,1xaamaa因因此此存存在在使使得得属属于于 的的,剩剩余余类类 1 (mod).aam 即即91()构构造造证证 性性证证明明二二( ,)1satma m( ,)1, ,a ms t 因因则则存存在在整整数数 1 (mod)aam 0 (mod),1 (mod),tmmsam因因 所所以以 (mod),asm 取取则则有有使使得得92 7,7mam 设设表表示示与与互互素素的的整整数数. .则则有有相相应应 例例的的同同余余式式 1 11 (mod7), 2 41 (mod7), 3 51 (mod7),4 21 (mod7), 5 31 (mod7), 6 61 (mod7) 5132

49、24 (mod737),a 取取则则 737,635,8ma设设由由广广义义欧欧几几里里例例得得除除法法, , 635 5131 (mod737) 224,193,( 224) 635193 7371st 可可得得整整数数使使9312121212211212(,)1, 0, 0, ,m mmmxxm mm xm xm m 设设若若分分别别遍遍历历的的简简化化剩剩余余系系 则则遍遍 历历模模的的简简化化剩剩余余系系. . 定定理理, , 5 521121212m xm xm mm m 因因简简化化剩剩余余系系是是一一个个完完全全剩剩余余系系中中一一切切与与模模互互素素的的数数作作成成的的. .

50、为为此此只只需需证证明明: :遍遍历历模模的的一一个个完完全全剩剩余余系系中中一一 切切与与模模互互分分析析: :素素的的整整数数. .1122211212(1) (,)(,)1(,)1x mxmm xm xm m12(,)1m m 利用利用,:为为此此 证证明明分分两两个个部部分分9421121122 (2) (,)1,(,)1.m mm x + m xx mxm模模的的任任一一简简化化剩剩余余系系可可表表为为其其中中1212 由2.2定理41121121(,)1(,)1(,)1x mm x mmm 证证 首首先先由由21121(,)1m xm xm2212212(,)1 (,)1(,)1x