《第二章同余与同余式》由会员分享，可在线阅读，更多相关《第二章同余与同余式（135页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章同余与同余式同余与同余式同余的概念与基本性质同余方程组的求解方法线性同余方程、高次同余方程的求解原根和指数应用第二章第二章同余与同余式同余与同余式在日常生活中,有时我们注意的常常不是某些整数,而是这些整数用某一个固定的整数去除所得到的余数.例如本月2日是星期3,那么9日,16日,都是星期3,这是因为它们用7除后得到的余数都是2在我国古代的干支纪年也是这样的,它是以60作为除数的纪年法.这样,在数学中就产生了同余的概念.同余概念是Gauss在1800年前后创立的.2.0同余定义同余定义和基本性质和基本性质定义定义1给定一正整数给定一正整数m,若用若用m去除两个整数去除两个整数a和和b
2、所得所得余数相同余数相同,则称则称a与与b为对模为对模m同余同余,记作记作a b(modm);若余数不同若余数不同,则称则称a与与b为对模为对模m不同余。不同余。a b(modm)iffm|(a-b).a 0(modm)iffm|a.性质性质:自反性自反性:a a(modm).对称性对称性:若若a b(modm),则则b a(modm).传递性传递性:若若a b(modm),b c(modm),则则:a c(modm).可见可见,同余关系是等价关系同余关系是等价关系.2.0同余式定义和基本性质定理定理1若若a b(modm),c d(modm),则则:ax+cy bx+dy(modm),其中其
3、中x和和y为任给整数为任给整数.ac bd(modm). 1)设设ab(modm),c是任意整数是任意整数.则则acbc(modm).2)设设aibi(modm)(i=1,2,n,n2),则则a1a2anb1b2bn (modm).an bn(modm),其中其中n0.f(a) f(b)(modm),其中其中f(x)为任意的一个整系数多为任意的一个整系数多项式项式.同余在算术里的两个应用：同余在算术里的两个应用：应用应用1检查因数的一些方法检查因数的一些方法一整数能被一整数能被3(9)整除整除iff它的十进位数码的和能被它的十进位数码的和能被3(9)整除整除.正整数正整数a=an1000n+a
4、n-11000n-1+ +a0 , 0ai3是一奇素数, S=2, 3, , p-2，aS. 因为(a,p)=1, 存在整数m和n, 使am+pn=1, 于是am1(mod p). 设b=m-pq, 即b是p除m的余数, 易知 b1, bp-1, 故 bS, 且 ab1(mod p). 可以证明 ab.定理定理(威尔逊定理威尔逊定理)P为素数为素数IFF(P-L)! -1(MODP). 假设 a=b, 则有(b-1)(b+1)0(mod p), 而 bl, b p-1, 故(b-1)(b+1)0(mod p)不成立. 可见S中的数可分成(p-3)/2对, 每一对数a和b, 满足 abl(mod
5、 p), 故得23(p-2) (mod p), 即可得(p-1)! -1 (mod p).定理定理(威尔逊定理威尔逊定理)P为素数为素数IFF(P-L)! -1(MODP).充分性充分性: 若(p-1)! = -l (mod p), 则 p为素数. 假设p是合数, 令 pab, ap. 由题设条件知, p|(p-1)!+l). 又因 a|p, 则有 a|(p-1)!+1). 但由于 ap-1可得 a|(p-1)!, 从而 a|(p-1)!+1)-(p-1)!), 即a|l, 因而p只有因子1和p, 即p为素数.同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余的应用同余的应用1：
6、国际图书标准：国际图书标准(ISBN编码编码) ISBN是是international standard of book number 的缩写，即国的缩写，即国际标准图书编号。际标准图书编号。ISBN是国际通用的图书或独立的出版物是国际通用的图书或独立的出版物(除定期出版除定期出版的期刊的期刊)代码。出版社可以通过代码。出版社可以通过ISBN清晰地辨认所有非期刊书籍。一个清晰地辨认所有非期刊书籍。一个ISBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版只有一个或一份相应的出版物与之对应。新版本如果在原来旧版的基础上没有内容上太大的变动，在出版时也不会得到新的的基础上没有内容上太大的
7、变动，在出版时也不会得到新的ISBN号码。号码。当平装本改为精装本出版时，原来相应的当平装本改为精装本出版时，原来相应的ISBN号码也应当收回。号码也应当收回。 国际标准图书编号问世后，很快得到推广，主要是因为它对出版国际标准图书编号问世后，很快得到推广，主要是因为它对出版商、书商的工作有很大的益处，体现在商、书商的工作有很大的益处，体现在:国际标准书号是机读的编码，国际标准书号是机读的编码，从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的作从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的作用用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书业它的引入使图书的
8、定购、库存控制、账目和输出过程等任何图书业的分支程序都简化了的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、采国际标准书号也对图书馆和文献中心的订购、采选、编目和流通程序都有促进作用选、编目和流通程序都有促进作用;ISBN系统的引入也服务于书目信息系统的引入也服务于书目信息的流动和使用，而且为一个国家的图书生产提供经济的书目控制的流动和使用，而且为一个国家的图书生产提供经济的书目控制;ISBN对图书市场更有效率，它能确定国际上出版的任何图书及其出版社。在对图书市场更有效率，它能确定国际上出版的任何图书及其出版社。在书业中习惯称书业中习惯称ISBN为库藏码为库藏码(Stock Num
9、ber)，就是因为其被普遍应用，就是因为其被普遍应用于书库管理。于书库管理。同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用10位数位数ISBN的结构的结构现行的现行的ISBN由由10位数字组成，这位数字组成，这10位数字由位数字由4组数字组成，中间用组数字组成，中间用“-”相连，每组数字都有不同的含义。相连，每组数字都有不同的含义。第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数字，大体上兼顾文种、国别和地区。字，大体上兼顾文种、国别和地区。0、1代表英语，使用这两个代码的国代表英语，使用这两个代码的
10、国家有家有:澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、美澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、美国、津巴布韦等国、津巴布韦等;2代表法语，法国、卢森堡以及比利时、加拿大和瑞士的代表法语，法国、卢森堡以及比利时、加拿大和瑞士的法语区使用该代码法语区使用该代码;3代表德语，德国、奥地利和瑞士德语区使用该代码代表德语，德国、奥地利和瑞士德语区使用该代码;4是日本出版物的代码是日本出版物的代码;5是俄罗斯出版物的代码是俄罗斯出版物的代码;7是中国出版物使用的代码。是中国出版物使用的代码。第二组第二组: 出版社代码。由国家或地区的出版社代码。由国家或地区的ISBN中心设置
11、并分给各个出版社。中心设置并分给各个出版社。第三组第三组:书序码。该出版物代码，是出版者分配给每一个出版物的编号。书序码。该出版物代码，是出版者分配给每一个出版物的编号。第四组第四组:计算机校验码。校验码是计算机校验码。校验码是ISBN号的最后一位数值，它能够校验出号的最后一位数值，它能够校验出ISBN号是否正确。校验码只能是号是否正确。校验码只能是1位数，当为位数，当为10时，记为罗马数字时，记为罗马数字X。同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用左图是左图是2007实行的新的实行的新的ISBN标准，从标准，从10位升到位升到13位，为了讲课方便，我们仍然位，为了讲课方便
12、，我们仍然用用2007年以前的年以前的10位标准来讲述：位标准来讲述：同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余的应用同余的应用2：验证信用卡的有效性：验证信用卡的有效性首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介绍国际上比较流行的绍国际上比较流行的Master卡，该卡标识码为卡，该卡标识码为16位，以位，以51，52，53，54或者或者55开头开头.比如：比如：5548 374
13、2 7983 0696在在Master卡中，具备如下性质：卡中，具备如下性质：1.如果第如果第2位为位为1，则第，则第2到到3位表示银行号。位表示银行号。2.如果第如果第2位为位为2，则第，则第2到到4位表示银行号。位表示银行号。3.如果第如果第2位为位为3，则第，则第2到到5位表示银行号。位表示银行号。4.如果第如果第2位为其他值，则第位为其他值，则第2到到6位表示银行号。位表示银行号。银行号后面直到第银行号后面直到第15位为持卡人账号，最后一位为校验位。比如刚才位为持卡人账号，最后一位为校验位。比如刚才的例子中，第的例子中，第2位为位为5，则银行号为，则银行号为54837，持卡人账号为，持
14、卡人账号为427983069同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用2.1一次同余式组一次同余式组本节介绍一次同余式组的解法及其应用举例在公元三世纪前,孙子算经里已提出了下面的同余式组xb1(mod m1), xb2(mod m2), xbk(mod mk) (1)这种形式的问题, 并且很好地解决了它.孙子算经里所提出的问题之一如下:“今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二. 问物几何？” “答日二十三.”15:51:432.1一次同余式组一次同余式组把这个问题的提法用同余式的式子来表达，它
15、可表示成解同余式组x2(mod 3), x3(mod 5), x2(mod 7)其中x是所求物数.关于同余式组:xa(mod 3), xb(mod 5), xb(mod 7) 的一般解为:x 70a+21b+15c (mod 105)15:51:432.1 一次同余式组这个解法, 在明朝程大位的算法统宗(1593)里有下面一首诗歌:三人同行七十稀，三人同行七十稀，五树梅花甘一枝，五树梅花甘一枝，七子团圆整半月，七子团圆整半月，除百零五便得知。除百零五便得知。关于解同余式组的问题, 在我国古代有极光辉的研究成果. 我国古代数学家孙子发明了下面的中外驰名的定理, 在国外誉为中国剩余定理, 在国内称
16、为孙子定理.15:51:432.1 一次同余式组定理定理1 一次同余式组一次同余式组x b1(mod m1), x b2(mod m2) (1)有解有解 iff (m1,m2)|(b1-b2), 且当且当(1)(1)有解时对模有解时对模 m1,m2有唯一解有唯一解. .证明：证明： 设(1)有解x0, (m1,m2)=d, 则有:x0b1(mod m1), x0b2(mod m2)m1=dq1, m2=dq2 于是, x0-b1=dq1m1, x0-b2=dq2m2, 因此, d|(b1- b2). 若(m1,m2)|(b1-b2),则因xb1(mod m1)可表示为: x=b1+m1y, 代
17、入xb2(mod m2)得: m1y(b2-b1)(mod m2) (2) 因为(m1,m2)=d, d|(b2-b1), (2)有解, 设为y0, 且对模m2/d有唯一解:yy0(mod (m2/d),15:51:432.1 一次同余式组证明证明(续续)：即 y=y0+km2/d, k=0,1, 2, . 因此(1)的全部解为: x=b1+m1y0+m1m2k/d, k=0,1, 2, . 这些解对模m1,m2是同余的, 故(1)的解对模m1,m2唯一.定理定理1 一次同余式组一次同余式组x b1(mod m1), x b2(mod m2) (1)有解有解 iff (m1,m2)|(b1-b
18、2), 且当且当(1)有解时对模有解时对模m1,m2有唯一解有唯一解.15:51:432.1一次同余式组一次同余式组对于一次同余式组对于一次同余式组: : x b1(mod m1), x b2(mod m2), x bk(mod mk), k3 3的情形的情形, , 可先解前两个得可先解前两个得x b1(modm1, ,m2), , 再与再与x b3(mod m3)联立解出联立解出x b3(modm1, ,m2, ,m3). . 如此如此继续下去继续下去, , 最后可得唯一解最后可得唯一解x bk(modm1, ,m2 ,mk). . 注注 若中间有一步出现无解若中间有一步出现无解, , 则同
19、余式组无解则同余式组无解. .15:51:432.1 一次同余式组定理定理2 (孙子定理孙子定理) )设设m1, m2, , mk是两两互素的是两两互素的k个正整数个正整数, , k=2, 并且并且m m1 m2 mk , m=miMi, 1ik, 则同余式则同余式组组(1)(1)有唯一解有唯一解x b1M1M1+b2M2M2+bkMkMk(mod m)(2)其中其中MiMi 1(mod mi), 1ik.证明证明: (mi,mj)=1, ij, 即得(Mi,mi)=1. 对每一Mi, 存在Mi, 使得MiMi 1(mod mi) (3)另一方面, 当ij时, 则由(mi,mj)=1和mmjM
20、j得到mi|Mj, 所以有:bjMjMj 0(mod mi) (4)15:51:432.1 一次同余式组由(3)和(4)有即(2)是(1)的解.若y也是(1)的解, 则得:xy(mod mi), 1ik于是, mi|(x-y), 1ik. 由于ml, m2, ,mk两两互素. 故m|(x-y), 即xy(mod m). 因此是(1)的唯一解.15:51:432.1 一次同余式组应用孙子定理可以证明如下定理.定理定理 3 设设m1,m2,mk是两两互素的是两两互素的 k个正整数个正整数, , mm1m2mk , ,则同余式则同余式: :f(x) 0 (mod m) (1) 有解有解 iff 同余
21、式组同余式组: :f(x) 0 (mod mi), 1ik (2) 的每个同余式有解的每个同余式有解, , 且若用且若用S表示表示(1)(1)的解数的解数, , Si表示表示(2)(2)的解数的解数, , 则则: : SS1S2Sk.15:51:432.1一次同余式组证明证明: 若x0是满足(1)的整数, 则由f(x0)0(mod m), 可得f(x0)0(mod mi), 1ik. 反之, 若xi满足(2), 1ik, 因为1ijk, (mi,mj)=1, 由孙子定理, 有唯一的x0, 0x0m, 满足x0 xi(mod mi), 1ik, 且f(x0) f(xi)0(mod mi), 1i
22、k. 故f(x0)0(mod m).充要条件得证。 现在设(2)有Si个不同解是xaiji(mod mi), 0aiji mi, 1ik , ljiSi, 对其中任一组a1ji, a2ji, akji, 由孙子定理可得唯一的x, 0xm, 是(1)的解, 且不同的组, 得到(1)的解也不同, 故SS1S2Sk.15:51:43例例1 韩信点兵:有兵一队, 若列成五行纵队, 则末行一人; 成六行纵队, 则末行五人; 成七行纵队,则末行四人; 成十一行纵队,则末行十人, 求兵数.解：解： 设x是所求兵数, 则依题意:x1(mod 5), x 5(mod 6)x4(mod 7), x 10(mod
23、11) 令m1=5,m2=6,m3=7,m4=11,b1=l, b2=5, b3=4, b4=10. 于是m=m1m2m3m4=567 11=2310, M1=2310/5=462, M2=385, M3=330, M4=210. 有M1M11(mod 5), 即1462 M1 2M1(mod 5) ,因此M1=3. 同理可求M2=1, M3=1, M4=1. 故解为:x 13462+15385+14330 + 110210 6731 2111(mod 2310). 即 x=2111+2310k, k=0,1,2,.2.2剩余类和剩余系剩余类和剩余系由于同余关系是等价关系, 因此对于给定的任一
24、工整数m, 利用模m同余这个关系, 可将整数集划分成m个等价类, 由于它是一些整数除m后的余数形成的, 所以称它是剩余类或同余类.于是有:定义定义1设设m是一给定的正整数是一给定的正整数,若若r=i:i r(modm),i Z,0rm-1则称则称r是是模模m剩余类剩余类.设a是任一整数, 则amq+r, 0rm, 故a恰包含在r中. 若a和b是两整数, 且在r中, 则amq1+r, b=mq2+r, 故m|(a-b). 反之, m|(a-b), 则由同余定义即知a和b同在某一类r中, 0rm.2.2剩余类和剩余系剩余类和剩余系定义定义2在模在模m剩余类剩余类0,1,m-1中各取一数中各取一数a
25、r r,0rm-1,该该m个数个数a0,a1,am-1称为模称为模m的一完的一完全剩余系全剩余系.若令若令x=a0,a1,am-1,则称则称x是过模是过模m的完的完全剩余系全剩余系.由此定义得以下定理.定理定理1m个整数构成模个整数构成模m的一完全剩余系的一完全剩余系iff两两对两两对模模m不同余不同余最常用的完全剩余系0,1,2,m-1, 称为模m的非负最小完全剩余系1,2 ,m, 称为模m的最小完全正剩余系2.2剩余类和剩余系剩余类和剩余系定理定理2设设a0,a1,am-1是模是模m的一完全剩余系的一完全剩余系,b是一整数是一整数,则则a0+b,a1+b,am-1+b也是模也是模m的一完全
26、剩余系的一完全剩余系.证明：证明： 假设(ai+b)(aj+b)(mod m), 0i2,a1b1,a2b2,anbn则不是模则不是模n的一完全剩余系的一完全剩余系.证明证明 读者可参见有关书籍的证明2.2 剩余类和剩余系下面介绍欧拉函数与简化剩余系定义定义3小于或等于小于或等于m且与且与m互素的正整数个数，记为中互素的正整数个数，记为中 (m),称为称为欧拉欧拉(Euler)函数函数.由定义知, (1)=1, (2)=1,(3)=2,(4)=2, (5)=4, (6)=2, (7)=6, (8)=4, (9)=6,.当p是素数时, (p)=p-1.2.2 剩余类和剩余系定理定理7设设p是一素
27、数是一素数,k是一正整数是一正整数,则则: (pk)=pk-1(p-1)证明证明 因为小于或等于pk且与pk不互素的正整数恰是p的各个倍数:1p,2p,3p,(pk-1)p显然共有pk-1个. 而小于或等于pk的正整数总共有pk个, 于是: (pk)= pk pk-1= pk-1 (p-1).2.2 剩余类和剩余系定义定义4若模若模m剩余类中的数与剩余类中的数与m互素互素,则称它为与模则称它为与模m互素的互素的剩余类剩余类,在与模在与模m互素的所有剩余类中互素的所有剩余类中,各取一数所组成各取一数所组成的集合的集合,称为模称为模m的一个的一个简化剩余系（缩系）简化剩余系（缩系）.由上面定义,
28、显然有下面二定理:定理定理8模模m简化剩余系含有中简化剩余系含有中 (m)个数个数.定理定理9若若a1,a2,a (m)是中是中 (m)个与个与m互素的整数互素的整数,a1,a2,a (m)是模是模m的一简化剩余系的一简化剩余系iff它们两两对模它们两两对模m不不同余同余.2.2 剩余类和剩余系定理定理10若若(a,m)=1,rl,r2,r (m)是模是模m的一简化剩余系的一简化剩余系,则则arl,ar2,ar (m)也是模也是模m的一简化剩余系的一简化剩余系.证明：证明： 只需证明arl,ar2,ar(m) 互不同余,且都与m互素即可. 假设ariarj(mod m), 其中1i, j (m
29、). 由于(a,m)=1, 故有rirj(mod m), 这与rl,r2,r(m)是模 m的一简化剩余系矛盾, 故ariarj(mod m), 即: arl,ar2,ar(m)两两互不同余. 假设p是m和某ari的公共素因数, 其中1i(m), 因p是素数, 故p|a或p|ri. 因此, p是a和m的公因数, 或是ri和m的公因数, 这与(a,m)=(ri,m)=l矛盾, (ari,m)=l, li(m) .即ari与m互素.2.2 剩余类和剩余系定理定理11(欧拉定理欧拉定理)设设m2,且且(a,m)=1,则则:a (m) 1(modm).证明证明: 设rl,r2,r(m)是模m的一简化剩余
30、系, 则由定理10知, rl,r2,r(m)也是模m的一简化剩余系. 故 (arl)(ar2)(ar(m)rlr2r(m) (mod m). 即 a(m) rlr2r(m) rlr2r(m) (mod m). 由于(ri,m)=1, 10, ai是整数, 0in, 则f(x)0(mod m) (1)称为模 m同余式. 若 an0(mod m), 称n是(1)的次数. 若 x0满足 f(x)0(mod m), 则 xx0(mod m)称为(1)的解. 注注：不同解是指互不同余的解.2.4 一次同余式注意, 若x0是(1)的解, 则模m的剩余类x0, 即全部整数x0+km, k=0, 1, 2,中
31、每一个都是满足(1), 而x0是x0非负最小整数, 即是非负最小剩余.由定义可知, 要求(1)的解, 只要逐个把0,1, 2, ,(m-1)代人(1)中进行验算即可.但当m大时, 计算量往往太大.下面就来讨论一元一次同余式的解的问题.2.4 一次同余式定理定理11设设(a,m)=1,m0,则则ax b(modm)(2)恰有一解恰有一解,且且x ba (m)-1(modm)证明证明 因为0,1,m-1是模m的一完全剩余系, (a,m)=1, 故0,a,2a,(m-1)a也是模m的一完全剩余系, 所以其中恰有一整数, 设为ka, 满足ka b(mod m), 即k满足(2)，因而xk(mod m)
32、是(2)的唯一解.由欧拉定理，立即可得xba (m)-1(mod m).2.4 一次同余式定理定理2设设(a,m)=d,m0,则则ax b(modm)(3)有解有解iffd|b证明证明 若(3)有解, 则由d|a, d|m, 推出d|b. 若d|b,则因(a/d,m/d)=1. 故由定理 1知: (a/d)x (b/d)(mod (m/d)有解, 即(3)有解.2.4 一次同余式定理定理3设设(a,m)=d,m0,d|b,则则ax b(modm)(4)恰有恰有d个解个解.证明证明 由d|b和定理2知(4)有解.显然, c为(4)的解 iff c也是:(a/d)x (b/d)(mod (m/d)
33、 (5) 的解. 令c满足(5), 则(5)有唯一解:x c(mod (m/d), 即整数c+k(m/d), k=0, 1, 2,.对于模m来说,恰可选出d个互不同余的整数:c, c+m/d, c+2m/d, c+(d-1)m/d定理定理3设设(A,M)=D,M0,D|B,则则AX B(MODM)(4)恰有恰有D个解个解.证明证明(续续)：这是因为对c+km/d, 令k=qd+r, 0rd, 代入c+km/d=c+(qd+r)m/dc+rm/d(mod m). 又若0ed, 0f0,an 0(modp),则同余式则同余式f(x) 0(modp)(1)最多有最多有n个解个解证明证明 对n进行归纳
34、. 当n=1时, 设一次同余式为a1x+a0 (mod p), p不能整除a1; 由于p不能整除a1; 故恰有一解. 现在, 假设定理对次数为n-1(n2)的同余式真, 欲证(1)最多有n个解.当np时结论显然成立, 故可设np-1. 用反证法, 假设同余式(1)有n+1个解: x0,x1,xn, xixj(模)(mod p), 0ijn, 这将导致矛盾.因为其中g(x)是首项系数为an的n-1次整数多项式,因此有但若k0, xk-x00(mod p), 故n-1次同余式g(x)0(mod p)有n个解, 与归纳假设矛盾.2.5 高次同余方程应用拉格朗日定理可得下面定理.定理定理2设同余式设同
35、余式的解的个数大于的解的个数大于n,其中其中p是素数是素数,ak是整数是整数,0kn,则则p|ak.证明：证明： 若某些系数不被p整除, 令其最大下标为k, 则kn. k次同余式: 的解的个数大于k, 这与定理5矛盾.2.5 高次同余方程定理定理3对于任给素数对于任给素数p,多项式多项式f(x)=(x-1)(x-2)(x-p+1)-xp-1+1的所的所有系数被有系数被p整除整除.证明证明 令g(x)=(x-1)(x-2)(x-p+1), 则1,2,p-1是同余式g(x)=0(mod p)的p-1个解. 由费马定理知, 1,2,p-1也是同余式 h(x)=xp-1-10(mod p)的p-1个解
36、. 故同余式f(x)=g(x)-h(x)(mod p)有p-1个解, 而f(x)是p-2次多项式, 由定理6知, 其所有系数被p整除.注意注意:本定理中f(0)=(-1)p-1(p-1)!+1, 而所有系数均被p整除, 故f(x)=(-1)p-1(p-1)!+10(mod p), 即有(p-1)! -1(mod p). 这又一次证明了威尔逊定理.2.5 高次同余方程下面对模 的同余方程做进一步讨论。 容易看出，若 是同余方程 f(x) 0 (mod ) (1) 的解，则它必是方程 f(x) 0 (mod ) (2) 的解，因此，必有与 相应的方程(2)的某个解 ，使 此处， 是某个适当的整数。
37、这提示我们：可以从方程(2)的解中去求方程(1)的解。于是，现在的问题是，对于方程(2)的每个解 ，是否必有方程(1)的解 与之对应？若有，如何去确定它？2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.6 原根本节围绕的是解高指数方程 xk a (mod m) 主要利用的是欧拉定理 欧拉定理的不足： 26 1 (mod 7) 同时23 1 (mod 7) 2.6.1 指数与原根 对xk 1 (mod m) ，肯定有解，但最小解？定义定义1 设 ,m 1,(a, m) = 1，则使 a d 1 (mod m) (1)成立的最小的正整数d，称
38、为a对模m的指数指数，记为ordm(a)，在不致误会的情况下，简记为ord(a)。指数也称为阶阶。2.6.1 指数与原根例如： ordm(1)=1, ord2(-1)=1, ordm(-1)=2(m2), ord17(3)=16注意：如果（a,m）1，则规定ordm(a)=0在谈到a对模m的指数时，总假定m1，(a, m) = 1。 有的使用ordm (a)等同的符号是 m(a)， (a)，但ordm (a)更常用2.6.1 指数与原根模7的指数表 11 1(mod 7) 23 1(mod 7) 36 1(mod 7) 43 1(mod 7) 56 1(mod 7) 62 1(mod 7)观察
39、： 2与4的指数同，3与5的指数同 所有的指数都是6的因数a123456ord7(a)1363622.6.1 指数与原根模10的指数表 11 1(mod 10) 34 1(mod 10) 74 1(mod 10) 92 1(mod 10) 观察： 3与7的指数同,是9的指数的2倍 所有的指数都是4的因数,4是什么？a1379ord10(a)14422.6.1 指数与原根定理定理1 1 指数的基本性质 an 1(modm)的充要条件是的充要条件是ordm( (a)|n)|n 分析：设n= ordm(a)q+r, 0r ordm(a), q,rZ，则： a n a ord(a)q+r a r 1
40、(mod m)， 因为ordm(a) 最小，所以r=0。推论：推论： ordm(a)| (m)定义定义2 若ordm (a)= (m)称a是模m的原根原根（也写作元根） 如，3和5是模7的原根，3和7是模10的原根原根也可能没有，如模15、8没有原根2.6.1 指数与原根例例 证明：5是模3与模6的原根，也是模32，2* 32的原根(3)=2， (6)=(3)(2)=2(32)=9-3=6, (2*32)=(2)(32)=65-1(mod 3) 521(mod 3) 5是模3的原根5-1(mod 6) 521(mod 6) 5是模6的原根55(mod 9) 52-2(mod 9) 53-1(m
41、od 9)544(mod 9) 552(mod 9) 561(mod 9) 5是模32原根55(mod 18) 527(mod 18) 53-1(mod 18)54-5(mod 18) 55-7(mod 18) 561(mod 18) 5是模2* 32原根2.6.1 指数与原根解：解： (17)=16,所以只需计算5的1、2、4、8、16次方55(mod 17) 528(mod 17) 5413(mod 17) 5816-1(mod 17) 5161(mod 17) 所以ord17(5)=16，5是模17的原根。例例 计算5模17的指数ord17(5)=？ 2.6.1 指数与原根定理定理1 指
42、数的基本性质 若若a b(modm)，(a,m)=1，则则ordm( (a)= )= ordm(b) 分析： a ord(a) b ord(b) a ord(b) b ord(a) 1 (mod m), 所以ordm(a)| ordm(b), ordm(b)| ordm(a) 所以ordm(a)=ordm(b)a-1a 1(modm)，则则ordm( (a)= )= ordm(a-1) 分析： (a-1a ) n 1(mod m)则 (a-1) n 1(mod m) a n 1(mod m) 2.6.1 指数与原根解：解：ord17(39)=ord17(5)=167*5=1(mod 17) o
43、rd17(7)=ord17(5)=16例例 计算39、7模17的指数2.6.1 指数与原根定理定理1 指数的基本性质记记n n=ordm( (a) ), ,则则a0,a1,an 1对模对模m两两不同余两两不同余。 分析：反证法.若0 i j n 1,使a i a j (mod m)， 则由(a, m) = 1 得到 a j i 1 (mod m)， 这与j-in = ordm(a) ,与指数的定义矛盾 所以定理成立. 特别的：特别的：g是原根是原根g0,g1,g(m) 1是模是模m的缩系的缩系思路：g1,g2,g (m) 这 (m)个数两两不同余，所以一定组成缩系;另一方面,g1,g2,g (
44、m)是缩系，所以当1l0, 0, ordm( (a i)=)=s s ，则则 。 分析： (a i)s 1 (mod m) n= ordm(a) |is 则最小的s= 。注：注： 当（i,n）=1时，幂后指数不变，此时i的个数为 （n）。 所以，有 （n）个与a 同指数, n= ordm(a) 。 所以，如果m有原根，则原根个数为 ( (m)。2.6.1 指数与原根例例 观察模7的所有缩系元素的指数ord7(2) =ord7(9)= ord = ord7(3) /(2, ord7(2) )=3ord7(4)= ord7(2)/(ord7(2),2) =3/(2,3)=3ord7(8)= 3/(
45、3,3)=1ord7(16)=3/(4,3)=3a123456ord7(a)1363622.6.1 指数与原根例例 观察模7的所有缩系元素的指数7的原根(7)=(6)=2个，6有因子1、2、3、6所以存在：3指数的(3)=2个2指数的(2)=1个1指数的(1)=1个a123456ord7(a)1363622.6.1 指数与原根解：解： 模7的原根的个数为 (7)=(6)=2，由前例， 3是模7的原根,6的缩系元素有1，5。所以35(mod 7) 3*22 12 5。所以模7的两个原根：3和5。例例 求出模7的所有原根2.6.1 指数与原根例例 计算计算7 7的缩系中每个元素的指数的缩系中每个元
46、素的指数方法1：依次计算幂（如前）方法2：首先找到一个原根，3(从2开始计算指数找原根)用此原根生成缩系：322, 336, 344, 355, 361 (mod 7)则：ord7(2)=6/(2,6)=3; ord7(6)=6/(3,6)=2;ord7(4)=6/(4,6)=3; ord7(5)=6/(5,6)=6;ord7(1)=6/(6,6)=1; 再加上ord7(3)=6。2.6.1 指数与原根定理定理1 指数的基本性质若若n m ，则则ordn( (a)| )| ordm( (a) ) 分析： a ordm (a) 1 (mod m) = a ordm (a) 1 (mod n) 对
47、于m=pe的情况特别有用若若(m,n)=1，(a,mn)=1，则则ordmn( (a)= )= ordm( (a),),ordn( (a) 分析：设s=ordm(a),ordn(a),t= ordmn(a),由 ordn(a)|t, ordm(a)|t =s|t; a s 1 (mod m) , a s 1 (mod n) = a s 1 (mod mn) = t|s 2.6.1 指数与原根解：解：(28)= (4) (7)=2*6=12本来需要计算幂为2、3、4、6但是因为ord7(3)=6，ord4(3)=2，所以6| ord28(3)现在只需直接计算361(mod 28)，所以ord28
48、(3)= 6上面利用的是 ，利用直接因为(4，7)=1，所以ord28(3)=6,2=6。例例 计算3模28的指数ord28(3)=？2.6.1 指数与原根解：解： (49)= 49-7=42ord7(3)=6，所以6| ord49(3)因为3681*9-17*9-2*3 -6(mod 49)所以ord49(3)= 42例例 计算3模49的指数ord49(3)=？2.6.1 指数与原根定理定理1 指数的基本性质 (ab,m)=1，( (ordm( (a),),ordm( (b)=1)=1则则ordm( (ab)=)=ordm( (a) )ordm( (b) ) 分析：设a ordm (b) o
49、rdm (ab) a ordm (b) ordm (ab) b ordm (b) ordm (ab) (a b) ordm (b) ordm (ab) 1 (mod m) = ordm(a)|ordm(b)ordm(ab),同理，ordm(b)|ordm(a)ordm(ab)所以， ordm(a)ordm(b)|ordm(ab)另一方面(a b) ordm (b) ordm (a) 1 (mod m) ,所以ordm(ab)|ordm(a)ordm(b)价值：简化求原根价值：简化求原根2.6.1 指数与原根解：解： (23)= 22，指数可能为1、2、11、22直接计算:224, 2111(m
50、od 23)，所以ord23(2)=11用以前的方法在计算3的幂，如不行在计算5的此时考虑只需找到一个ord23(a)=2，则ord23(2a)=22而ord23(-1)=2所以ord23(-2)=22，-2是原根，所以原根有(22)=10个(-2)315,(-2)514,(-2)710,(-2)917,(-2)1319(mod 23)(-2)157,(-2)175,(-2)1920,(-2)2111 (mod 23)所以模23的原根有：5,7,10,11,14,15,17,19,20,21。计算模23的原根2.6.2原根的存在条件对于什么样的正整数m，模m的原根是存在?下面的定理不用证明，只
51、需应用定理定理 若若p是奇素数，则原根存在是奇素数，则原根存在.定理定理 若若p是奇素数，是奇素数，g是模是模p的一个原根，则的一个原根，则g或或g+p是模是模p2的原根，若的原根，若g是模是模p2的原根，则的原根，则g是模是模p 的原根的原根.定理定理 模模m有原根的必要条件是有原根的必要条件是m=2，4，p 或或2p ，其其中中p是奇素数是奇素数， 1 .2.6.3 模素数原根的计算技巧定理定理 设奇素数p，p-1= ，(pi是素数)，若a与p互素，且 ， i=1,2,s 则a为p的原根。思路：设ordp(a)=n，则n|p-1，若np-1则存在某个素数pi|(p-1)/n即： (p-1)
52、/n= pi u从而，与条件矛盾，所以n=p-1。练习例例 求模47的一个原根解： 首先分解47-1=2*23(a,47)=1,取a=2, 223 1 (mod 47)，失败取a=3, 323 1 (mod 47)，失败取a=5, 523 -1 (mod 47)， 52 25(mod 47)，所以5是模47的一个原根2.6.4 指标定义定义1 设m是大于1的整数，g是其一个原根，(a,m)=1，则存在唯一整数r (0 r (m)1)使 gr a (mod m) 则r叫做以g为底的a对模m的一个指标指标，记为r=indga注：类似于对数，所以这个解方程问题叫做离散对数问题。离散对数问题。2.6.
53、4 指数7的指数表填表规则 a所在行作乘法 ，ind a 所在行作加法 ind a为1时，对应的a为起始的那个原根a123456ind3a021453aa2a3a4a5a663264512练习类似于解对数方程：5ind3x ind33 1(mod 6) 为什么是6?ind3x 5(mod 6)查表 x5(mod 7) 注意：模又恢复为7当然也可以利用 ind5x5ind5x ind53 5(mod 6) ind5x 1(mod 6)直接 x5(mod 7)例例 解方程 x5 3 (mod 7)a123456ind3a021453练习法一： 6-1 -1 (mod 7)，所以原方程化简为3x -
54、5 2(mod 7)，所以xind33 ind32(mod 6) x2(mod 6) 仍然是6法二：ind36+xind33 ind35(mod 6) 3+x5(mod 6)x2(mod 6) 仍然是6指数模指数，底数模m例例 解方程 6*3x 5 (mod 7)a123456ind3a021453三大难题之一三大难题之一：离散对数问题gr a (mod m)，已知g,a,m，求r困难。当g、m、r已知时，用快速指数算法可比较容易地求出a，但如果已知g,a,m ，求r则非常困难。目前已知的最快的求离散对数算法其时间复杂度为(m=p)：所以当p很大时，该算法也是不可行的。2.6.5 应用应用2.
55、6.5 应用三大难题之一三大难题之一：离散对数问题gr a (mod m)，已知g,a,m，求r困难EIGamal公钥密码体制公钥密码体制(1)选取大素数p和p的一个原根a，(a,p)=1,1ap(2)选取整数d，1dp-1，计算b ad (mod p)；p,a,b为公钥，d为私钥(3)加密：对0mp，秘密的随机选取整数k,1kp-1,加密后密文为c=(c1 ， c2 ), c1 ak (mod p), c2 mbk (mod p)(4)解密：明文m c2 ( c1 d) -1 (mod p)分析： c2 ( c1 ) -d mbk (ak d) -1 m adk (ak d) -1 m (m
56、od p)应用密钥交换密钥交换对称加密需要Diffie-Hellman密钥交换密钥交换素数p与其原根a为公开整数设A,B希望交换密钥，则A选择随机数XAp，计算YA aXA(mod p)；类似的B选择随机数XBp，计算YB aXB(mod p)，X私有，Y公开A计算KA(YB)XA(mod p)将其作为自身密钥B计算KB(YA)XB(mod p)将其作为自身密钥KA= KB实现了密钥的交换应用RSA定点攻击定点攻击第三者截获密文C后，反复计算e次幂 ce me2 ce2 me3 （mod n）一旦 cet c me（mod n） = m ce(t-1) （mod n） t不是很大时这种攻击可行
57、如何避免？如何让t很大？若m模n的指数为k，t可取的最小值为e模k的指数这个指数为(k)的因子，所以(k)应有大素因子而k是(n)=(p-1)(q-1)的因子所以p-1,q-1应有大素因子强素数 总结原根缩系中指数与欧拉函数相等的数模m有原根的必要条件是m = 2，4，p或2p，其中p是奇素数， 1指数：ak 1 (mod m)成立的最小正整数k,写作ordm(a) 或m(a)若指数与欧拉函数不等，指数也整除欧拉函数等指数：同余、互逆数的指数相同如何计算指数？幂从小到大取欧拉函数的因数试算，直到1如何计算原根计算出的指数等于欧拉函数练习计算ord11(3)首先计算(11)=10，所以指数可能为
58、1,2,5,10从小到大依次试算313, 329, 351(mod 11)，所以ord11(3)=5根据这个结论可以推出 ord11(14)=5=ord11(4)可以推出ord11(-3)= ord11(-1)* ord11(3)=10所以-38是原根，原根一共(10)=4个所以823，8329 726， 87221212， 89227277，即2、6、7、8是原根总结寻找一个原根的技巧:ordm(a) |(m)(m, n) = 1，(a, mn) = 1，则ordmn(a)= ordm(a),ordn(a)(ab, m) =1， (ordm(a),ordm(b)=1则ordm(ab)=ord
59、m(a)ordm(b)奇素数p，p-1=练习求模41的原根情况(11)=40,现在只要考察x8, x20从2开始,因为2810, 2201(mod 41);381, 320-1(mod 41);4820, 4201(mod 41);5818, 5201(mod 41);6810, 620-1(mod 41);所以6是模41的原根练习求模41的原根情况因为:6236, 63-3011, 6425, 65-5527(mod 41);6639, 6729, 6810, 6919,61032, 61128(mod 41);6124, 61324, 61421, 6153, 61618, 61726(m
60、od 41);61833, 61934, 62040,62135,6225, 62330 (mod 41);62416, 62514,6262,62712, 62831, 62922 (mod 41);6309, 63113, 63237,63317,63420, 63538(mod 41);63623, 63715, 6388,6397,6401(mod 41);练习求模41的原根情况所以:指数为1的元素有(1)=1个,是1;指数为2的元素有(2)=1个,是62040 (mod 41);指数为4的元素有(4)=2个,是61032, 6309(mod 41);指数为5的元素有(5)=4个,是1
61、0，18，16，37指数为8的元素有(8)=4个,是27，3，14，38指数为10的元素有(10)=4个,是25，4，31，23指数为20的元素有(20)=8个,是36，39，21，33，5，2，20，8指数为40的元素有(40)=16个,是6，11，29，19，28，24，26，34，35，30，12，22，13，17，15，7总结指数的价值：幂化简原根的价值生成元：生成缩系所有元素,gdd遍历(p)的缩系(p)个)，gd遍历模p的原根g是原根的时候幂与(计算幂后的)值形成置换aa2a3a4a5a6326451总结原根的价值之二可以推出其余所有缩系元素的指数ordm(ai)=ordm(a)/
62、(ordm(a),i)可以根据幂对缩系元素按指数分类a7a8a9a107361aa2a3a4a5a62485109练习计算同余方程xk 1 (mod 11)的解的个数n首先计算(11)=10，所以指数可能为1,2,5,10nk=1时，有(1)=1个；nk=2时，有(2)=1个nk=5时，有(5)=4个；nk=10时，有(10)=4个n考虑不周，k=3,4等其他数时呢x 1 (mod 11)是k等于任何值的解练习计算同余方程xk 1 (mod 11)的解的个数关键在于指数可能可以化简指数可取1,2,5,10,指数为1时，有1个解，此时k可取1的倍数，即1-10任意数指数为2时，有1个解，此时k取
63、2的倍数，即2,4,6,8,10指数为5时，有4个解，此时k取5的倍数，即5,10指数为10时，有4个解，此时k取10综合：k=1,3,7,9有1个解，k=2,4,6,8有两个解，k=5有5个解，k=10有10个解练习进一步：xk 1 (mod 11)各有哪些解？先找出每个指数对应的解，要计算指数先找出原根原根都是试找的，先看2224, 25-1, 2101(mod 11),所以2是模11的原根所以生成缩系中的其它元素224, 238, 245, 2510, 269 (mod 11)277, 283, 296, 2101 (mod 11)所以原根有：2、8、7、6（幂与10互质）指数为5的有：
64、4、5、9、3（幂与10最大公约2）指数为2的有：10指数为1的有1练习进一步：xk 1 (mod 11)各有哪些解？所以原根有：2、8、7、6（幂与10互质）指数为5的有：4、5、9、3（幂与10最大公约2）指数为2的有：10指数为1的有1所以k=1、3、7、9时有解x1(mod 11)k=2、4、6、8时有解x1(mod 11)和x10(mod 11)k=5时有解x1,3,4,5,9(mod 11)K=10时有解x1,2,3,4,5,6,7,8,9,10(mod 11)2.6.6 初等数论在计算机科学技术中的几个应用费马小定理的应用费马小定理的应用费马小定理 设p是素数, a与p互素, 则
65、 ap-11(mod p).另一种形式另一种形式是, 设p是素数, 则对任意的整数a, apa(mod p). 费马小定理提供了一种不用因子分解就能断定一不用因子分解就能断定一个数是合数个数是合数的新途径. 例如, 2914 (mod 9), 可以断定9是合数. 2.6.6 初等数论在计算机科学技术中的几个应用产生均匀伪随机数的方法产生均匀伪随机数的方法随机数与伪随机数线性同余法与乘同余法随机数随机数： 随机变量的观察值伪随机数伪随机数： 用计算机随机函数所产生的“随机数”并不随机，是伪随机数。 (0,1)上的均匀分布上的均匀分布U(0,1): a(0a1), P0Xa=a2.6.6 初等数论
66、在计算机科学技术中的几个应用线性同余法线性同余法 选择4个非负整数: 模数m, 乘数a, 常数c和种子数x0, 其中2am, 0cm, 0x0m, 用递推公式产生伪随机数序列: xn=(axn 1+c)modm,n=1,2,取 un=xn/m, n=1,2,作为U(0,1)伪随机数. 线性同余法产生的序列的质量取决于质量取决于m,a和和c. 例如m=8, a=3, c=1, x0=2, 得到7,6,3,2,7,6,周期为4 m=8, a=5, c=1, x0=2, 得到3,0,1,6,7,4,5,2,3,0,1, 周期为8. a=0, 得到c, c, c,a=1, 得到x0+c, x0+2c, x0+3c, 2.6.6 初等数论在计算机科学技术中的几个应用乘同余法乘同余法: c=0(x00)的线性同余法, 即 xn=axn 1modm,n=1,2,.最常用的均匀伪随机数发生器:m=2311, a=75的乘同余法,它的周期是2312.作业P34 2.5补充练习：1. 解同余方程：x12 16 (mod 17)。2. 设m 3，g1和g2都是模m的原根，则g = g1g2不是模m的原根。
