第二章同余与同余式

1、第二章第二章 同余与同余式同余与同余式 同余的概念与基本性质同余方程组的求解方法线性同余方程、高次同余方程的求解原根和指数应用第二章第二章 同余与同余式同余与同余式 在日常生活中,有时我们注意的常常不是某些整数,而是这些整数用某一个固定的整数去除所得到的余数.例如本月2日是星期3,那么9日,16日,都是星期3,这是因为它们用7除后得到的余数都是2在我国古代的干支纪年也是这样的,它是以60作为除数的纪年法.这样,在数学中就产生了同余的概念.同余概念是Gauss在1800年前后创立的.2.0 2.0 同余定义同余定义和基本性质和基本性质定义定义1 1 给定一正整数给定一正整数m, m, 若用若用m

2、m去除两个整数去除两个整数a a和和b b所得所得余数相同余数相同, , 则称则称a a与与b b为对模为对模mm同余同余, , 记作记作a a b(mod m); b(mod m); 若余数不同若余数不同, , 则称则称 a a与与b b为对模为对模mm不同余。不同余。a a b(mod m) iff m|(a-b).b(mod m) iff m|(a-b).a a 0(mod0(mod m) iff m| a. m) iff m| a.性质性质: : 自反性自反性: : a a a (mod m).a (mod m). 对称性对称性: : 若若a a b(mod m), b(mod m),

3、 则则 b b a(mod m).a(mod m). 传递性传递性: : 若若a a b(mod m), bb(mod m), b c(mod m), c(mod m), 则则: : a a c(mod m).c(mod m).可见可见, , 同余关系是等价关系同余关系是等价关系. .2.0同余式定义和基本性质定理定理1 1 若若a a b(mod m), cb(mod m), c d(mod m), d(mod m), 则则: : ax+cy ax+cy bx+dy(mod m), bx+dy(mod m), 其中其中x x和和y y为任给整数为任给整数. . ac ac bd(mod m)

4、. bd(mod m). 1) 设设a b (modm), c是任意整数是任意整数.则则 ac bc(modm). 2) 2) 设设ai bi (modm)(i =1,2,n, n2),n, n2),则则 a1a2an b1b2bn (modm). a an n b bn n(mod m), (mod m), 其中其中 n n0.0. f(a) f(a) f(b)(mod f(b)(mod m), m), 其中其中f(x)f(x)为任意的一个整系数多为任意的一个整系数多项式项式. .同余在算术里的两个应用：同余在算术里的两个应用：应用应用11检查因数的一些方法检查因数的一些方法 一整数能被一整

5、数能被3(9)3(9)整除整除 iff iff 它的十进位数码的和能被它的十进位数码的和能被 3(9) 3(9)整除整除. .正整数正整数a=a=an1000n+an-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 p为素数为素数 iffiff (p-l)! (p-l)! -1(mod p).-1(

6、mod p). 假设 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 p), 故得23(p-2) (mod p), 即可得(p-1)! -1 (mod p).定理定理 ( (威尔逊定理威尔逊定理) ) p p为素数为素数 iffiff (p-l)! (p-l)! -1(mod p).-1(mod p).充分性充分性: 若(p-1)! = -l (mod p), 则 p为素数. 假设p是合数, 令 pab, ap. 由题设条件知, p|(p

7、-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：国际图书标准：国际图书标准(ISBN编码编码) ISBN是是international standard of book number 的缩写，即国的缩写，即国际标准图书编号。际标准图书编号。ISBN是国际通用的图书或独立的出版物是国际通用的图书或独立的出版物(除定期出版除定期出版的期刊的期刊)代码。出版社可以

8、通过代码。出版社可以通过ISBN清晰地辨认所有非期刊书籍。一个清晰地辨认所有非期刊书籍。一个ISBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版只有一个或一份相应的出版物与之对应。新版本如果在原来旧版的基础上没有内容上太大的变动，在出版时也不会得到新的的基础上没有内容上太大的变动，在出版时也不会得到新的ISBN号码。号码。当平装本改为精装本出版时，原来相应的当平装本改为精装本出版时，原来相应的ISBN号码也应当收回。号码也应当收回。 国际标准图书编号问世后，很快得到推广，主要是因为它对出版国际标准图书编号问世后，很快得到推广，主要是因为它对出版商、书商的工作有很大的益处，体现在商、

9、书商的工作有很大的益处，体现在:国际标准书号是机读的编码，国际标准书号是机读的编码，从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的作用作用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书它的引入使图书的定购、库存控制、账目和输出过程等任何图书业的分支程序都简化了业的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、国际标准书号也对图书馆和文献中心的订购、采选、编目和流通程序都有促进作用采选、编目和流通程序都有促进作用;ISBN系统的引入也服务于书目信系统的引入也服务于书目信息的流动和使用，而且为一个国家

10、的图书生产提供经济的书目控息的流动和使用，而且为一个国家的图书生产提供经济的书目控制制;ISBN对图书市场更有效率，它能确定国际上出版的任何图书及其出对图书市场更有效率，它能确定国际上出版的任何图书及其出版社。在书业中习惯称版社。在书业中习惯称ISBN为库藏码为库藏码(Stock Number)，就是因为其被，就是因为其被普遍应用于书库管理。普遍应用于书库管理。同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用10位数位数ISBN的结构的结构现行的现行的ISBN由由10位数字组成，这位数字组成，这10位数字由位数字由4组数字组成，中间用组数字组成，中间用“-”相连，每组数字都有不同的

11、含义。相连，每组数字都有不同的含义。第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数字，大体上兼顾文种、国别和地区。字，大体上兼顾文种、国别和地区。0、1代表英语，使用这两个代码的国代表英语，使用这两个代码的国家有家有:澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、美澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、美国、津巴布韦等国、津巴布韦等;2代表法语，法国、卢森堡以及比利时、加拿大和瑞士的代表法语，法国、卢森堡以及比利时、加拿大和瑞士的法语区使用该代码法语区使用该代码;3代表德语，德国、奥地

12、利和瑞士德语区使用该代码代表德语，德国、奥地利和瑞士德语区使用该代码;4是日本出版物的代码是日本出版物的代码;5是俄罗斯出版物的代码是俄罗斯出版物的代码;7是中国出版物使用的代码。是中国出版物使用的代码。第二组第二组: 出版社代码。由国家或地区的出版社代码。由国家或地区的ISBN中心设置并分给各个出版社。中心设置并分给各个出版社。第三组第三组:书序码。该出版物代码，是出版者分配给每一个出版物的编号。书序码。该出版物代码，是出版者分配给每一个出版物的编号。第四组第四组:计算机校验码。校验码是计算机校验码。校验码是ISBN号的最后一位数值，它能够校验出号的最后一位数值，它能够校验出ISBN号是否正

13、确。校验码只能是号是否正确。校验码只能是1位数，当为位数，当为10时，记为罗马数字时，记为罗马数字X。同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用左图是左图是2007实行的新的实行的新的ISBN标准，从标准，从10位升到位升到13位，为了讲课方便，我们仍然位，为了讲课方便，我们仍然用用2007年以前的年以前的10位标准来讲述：位标准来讲述：12912910ISBNx ,x ,x ,x +2x9xx (mod11)4,假设号已经选择前9位则这最后一位校验位为：1比如：有一本书的前9位为0-619-06213,则其校验位由以下确定：(1 0+2 6+3 1+4 9+5 0+6 6+

14、7 2+8 1+9 3)(mod11)=136(mod11)(mod11)故该书的校验码为4同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用12101210kkiiiiii1234567891012i-1ii 191012iISBNx xxy yyyxkiyxx yxya0a101y2y3y4y5y6y7y8y9y10y1x2x(i1)xiy(i1)x9x10 x1x2x(i1)x定理：通过校验位可以发现的单一错误。证明：假设变成，其中（）,。不妨设，必存在整数使得。其中。因此-1ii 191010ii 110ii 1123456789101234567891010ixi(-a)(

15、i1)x9x10 xixi(-a)i(-a)mod(11)ix0mod(11)1x2x3x4x5x6x7x8x9xxmod(11)1x2x3x4x5x6x7x8x9x10 x11xmod(11)0mod(1注意到此时，这是因为则必有101210ii 112101)y yyISBNiy0mod(11)i(-a)0mod(11)11 ia1i10 0a10,y yyISBN如果是正确的号，则，由此。则，但是，不可能，故不是正确的号同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用1ij101ji10 xxxxxxxx类似的可以证明如下的定理：定理：通过校验位可以发现不等位互换的错误。即是

16、形如变成的错误。同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用同余的应用同余的应用2：验证信用卡的有效性：验证信用卡的有效性首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介绍国际上比较流行的绍国际上比较流行的Master卡，该卡标识码为卡，该卡标识码为16位，以位，以51，52，53，54或者或者55开头开头.比如：比如：5548 3742 7983 0696在在Master卡中，具备如下性质：卡中，具备如下性质：1.如果第如果第2位为位为1，则第，则第2到到3位表示银行号。位表示银行号。2.如果第如果第2位

17、为位为2，则第，则第2到到4位表示银行号。位表示银行号。3.如果第如果第2位为位为3，则第，则第2到到5位表示银行号。位表示银行号。4.如果第如果第2位为其他值，则第位为其他值，则第2到到6位表示银行号。位表示银行号。银行号后面直到第银行号后面直到第15位为持卡人账号，最后一位为校验位。比如刚才位为持卡人账号，最后一位为校验位。比如刚才的例子中，第的例子中，第2位为位为5，则银行号为，则银行号为54837，持卡人账号为，持卡人账号为427983069同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用1 216Ma aaMSasteraster卡的标识码，确定卡的校验位，使用以下算法：

18、1.从右边第2位往左，将每隔一位乘以22.将第1步中的积各位相加。3.将第1步没有乘以2的各位相加4.将第2步和第3步的结果相加5.如果第4步得到的结果为S，则如果0（mod10），则该卡有效，否则无效同余关系及其在计算机领域的应用同余关系及其在计算机领域的应用:55461997 23355004mod例 假设信用卡的标志码为，检查该卡的有效性。解：1.0 2=0 5 2=10 3 2=6 2 2=4 9 2=18 1 2=2 4 2=8 5 2=102.0+1+6+4+9+2+8+1=313.5+6+9+7+3+5+0+4=394.31+39=705.700（10）所以这张卡的标志码有效。2

19、.1 2.1 一次同余式组一次同余式组本节介绍一次同余式组的解法及其应用举例在公元三世纪前,孙子算经里已提出了下面的同余式组xb1(mod m1), xb2(mod m2), xbk(mod mk) (1)这种形式的问题, 并且很好地解决了它.孙子算经里所提出的问题之一如下:“今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二. 问物几何？” “答日二十三.”15:51:432.1 2.1 一次同余式组一次同余式组把这个问题的提法用同余式的式子来表达，它可表示成解同余式组x2(mod 3), x3(mod 5), x2(mod 7)其中x是所求物数.关于同余式组:xa(mod 3)

20、, xb(mod 5), xb(mod 7) 的一般解为:x 70a+21b+15c (mod 105)15:51:432.1 一次同余式组这个解法, 在明朝程大位的算法统宗(1593)里有下面一首诗歌:三人同行七十稀，三人同行七十稀，五树梅花甘一枝，五树梅花甘一枝，七子团圆整半月，七子团圆整半月，除百零五便得知。除百零五便得知。关于解同余式组的问题, 在我国古代有极光辉的研究成果. 我国古代数学家孙子发明了下面的中外驰名的定理, 在国外誉为中国剩余定理, 在国内称为孙子定理.15:51:432.1 一次同余式组定理定理1 1 一次同余式组一次同余式组x x b b1 1(mod m(mod

21、m1 1), x), x b b2 2(mod m(mod m2 2) (1) (1)有解有解 iff (miff (m1 1,m,m2 2)|(b)|(b1 1-b-b2 2), ), 且当且当(1)(1)有解时对模有解时对模 mm1 1,m,m2 2 有唯一解有唯一解. .证明：证明： 设(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+m1

22、y, 代入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,m

23、2)|(b1-b2), 且当且当(1)有解时对模有解时对模m1,m2有唯一解有唯一解.15:51:432.1 2.1 一次同余式组一次同余式组对于一次同余式组对于一次同余式组: : x x b b1 1(mod m(mod m1 1), x), x b b2 2(mod m(mod m2 2), ), x x b bk k(mod m(mod mk k), k), k3 3的情形的情形, , 可先解前两个得可先解前两个得x x b b1 1(modm(modm1 1, ,mm2 2) ), , 再与再与x x b b3 3(mod m(mod m3 3) )联立解出联立解出x x b b3 3

24、(modm(modm1 1, ,mm2 2, ,mm3 3) ). . 如此继续如此继续下去下去, , 最后可得唯一解最后可得唯一解x x b bk k(modm(modm1 1, ,mm2 2 ,mmk k) ). . 注注 若中间有一步出现无解若中间有一步出现无解, , 则同余式组无解则同余式组无解. .15:51:432.1 一次同余式组定理定理2 (2 (孙子定理孙子定理) )设设mm1 1, m, m2 2, , , , mmk k是两两互素的是两两互素的k k个正整数个正整数, , k k=2, =2, 并且并且mm m m1 1 m m2 2 mmk k , m= , m=mmi

25、 iMMi i, 1ik, , 1ik, 则同余则同余式组式组(1)(1)有唯一解有唯一解x x b b1 1MM1 1MM1 1+b+b2 2MM2 2MM2 2+b bk kMMk kMMk k(mod m)(2)(mod m)(2)其中其中MMi iMMi i 1(mod m1(mod mi i), 1ik.), 1ik.证明证明: : (mi,mj)=1, ij, 即得(Mi,mi)=1. 对每一Mi, 存在Mi, 使得MiMi 1(mod mmi i) (3)另一方面, 当ij时, 则由(mi,mj)=1和mmjMj得到mi|Mj, 所以有:bjMjMj 0(mod mi) (4)1

26、5: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)的唯一解.kimbMMbMMbiiiiikjjjj1),(mod1)(mod1mMMbxkjjjj15:51:432.1 一次同余式组应用孙子定理可以证明如下定理.定理定理 3 3 设设mm1 1,m,m2 2,m,mk k是两两互素的是两两互素的 k k个正整数个正整数, , mmmm1 1mm2 2mmk k , ,则同余式则同余

27、式: :f(x)f(x) 0 (mod m) (1)0 (mod m) (1) 有解有解 iff iff 同余式组同余式组: :f(x)f(x) 0 (mod m0 (mod mi i), 1ik (2), 1ik (2) 的每个同余式有解的每个同余式有解, , 且若用且若用S S表示表示(1)(1)的解数的解数, , S Si i表示表示(2)(2)的解的解数数, , 则则: : S SS S1 1S S2 2SSk k. .15:51:432.1一次同余式组证明证明: : 若x0是满足(1)的整数, 则由f(x0)0(mod m), 可得f(x0)0(mod mi), 1ik. 反之, 若

28、xi满足(2), 1ik, 因为1ijk, (mi,mj)=1, 由孙子定理, 有唯一的x0, 0 x0m, 满足x0 xi(mod mi), 1ik, 且f(x0) f(xi)0(mod mi), 1ik. 故f(x0)0(mod m).充要条件得证。 现在设(2)有Si个不同解是xaiji(mod mi), 0aiji mi, 1ik 1ik , ljiSi, 对其中任一组a1ji, a2ji, akji, 由孙子定理可得唯一的x, 0 xm, 是(1)的解, 且不同的组, 得到(1)的解也不同, 故SS1S2Sk.15:51:43例例1 1 韩信点兵:有兵一队, 若列成五行纵队, 则末行

29、一人; 成六行纵队, 则末行五人; 成七行纵队,则末行四人; 成十一行纵队,则末行十人, 求兵数.解：解： 设x是所求兵数, 则依题意:x1(mod 5), x 5(mod 6)x4(mod 7), x 10(mod 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 134

30、62+15385+14330 + 110210 6731 2111(mod 2310). 即 x=2111+2310k, k=0,1,2,.2.2 2.2 剩余类和剩余系剩余类和剩余系由于同余关系是等价关系, 因此对于给定的任一工整数m, 利用模m同余这个关系, 可将整数集划分成m个等价类, 由于它是一些整数除m后的余数形成的, 所以称它是剩余类或同余类.于是有:定义定义1 1 设设mm是一给定的正整数是一给定的正整数, , 若若 r = i: ir = i: i r(mod m), ir(mod m), i Z, 0rm-1Z, 0rm-1 则称则称 r r是是模模mm剩余类剩余类. .设a

31、是任一整数, 则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.2 剩余类和剩余系剩余类和剩余系定义定义2 2 在模在模mm剩余类剩余类0, 1, 0, 1, ,m-1,m-1中各取一数中各取一数a ar r r, 0rm-1, r, 0rm-1, 该该mm个数个数a a0 0,a,a1 1,a,am-1m-1称为模称为模mm的一的一完全剩余系完全剩余系. . 若令若令x=ax=a0 0,a,a1 1,a,am-1m-1, ,

32、 则称则称x x是过模是过模mm的的完全剩余系完全剩余系. .由此定义得以下定理.定理定理1 1 m m个整数构成模个整数构成模mm的一完全剩余系的一完全剩余系 iff iff 两两两两对模对模 mm不同余不同余最常用的完全剩余系0,1,2,m-1, 称为模m的非负最小完全剩余系1,2 ,m, 称为模m的最小完全正剩余系2.2 2.2 剩余类和剩余系剩余类和剩余系定理定理2 2 设设a a0 0,a,a1 1,a,am-1m-1是模是模mm的一完全剩余系的一完全剩余系, , b b是一整数是一整数, , 则则a a0 0+b,a+b,a1 1+b, ,a+b, ,am-1m-1+ +b b也是

33、模也是模mm的一完全剩余系的一完全剩余系. .证明：证明： 假设(ai+b)(aj+b)(mod m), 0i2, an2, a1 1b b1 1,a,a2 2b b2 2,a,an nb bn n 则不是模则不是模n n的一完全剩余的一完全剩余系系. .证明证明 读者可参见有关书籍的证明2.2 剩余类和剩余系下面介绍欧拉函数与简化剩余系定义定义3 3 小于或等于小于或等于mm且与且与mm互素的正整数个数，记为中互素的正整数个数，记为中 ( (m), m), 称为称为欧拉欧拉( (Euler)Euler)函数函数. .由定义知, (1)=1, (2)=1, , (3)=2, (4)=2, (5

34、)=4, (6)=2, (7)=6, (8)=4, (9)=6,.当p是素数时, ( (p p)=p-1.)=p-1.2.2 剩余类和剩余系定理定理7 7 设设p p是一素数是一素数, , k k是一正整数是一正整数, , 则则: : ( (p pk k)=p)=pk-1k-1(p-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 4 若模若模mm剩余类中的数与剩余类中的数与m

35、m互素互素, , 则称它为与模则称它为与模mm互素互素的剩余类的剩余类, , 在与模在与模mm互素的所有剩余类中互素的所有剩余类中, , 各取一数所组成各取一数所组成的集合的集合, , 称为模称为模mm的一个的一个简化剩余系（缩系）简化剩余系（缩系）. .由上面定义, 显然有下面二定理:定理定理8 8 模模mm简化剩余系含有中简化剩余系含有中 ( (m)m)个数个数. .定理定理9 9 若若a a1 1,a,a2 2,a,a (m)(m)是中是中 (m)(m)个与个与mm互素的整数互素的整数, , a a1 1,a,a2 2,a,a (m)(m)是模是模mm的一简化剩余系的一简化剩余系 iff

36、 iff 它们两两对模它们两两对模mm不同余不同余. .2.2 剩余类和剩余系定理定理 10 10 若若( (a,m)=1, ra,m)=1, rl l,r ,r2 2,r,r (m)(m)是模是模 mm的一简化剩余系的一简化剩余系, , 则则ararl l,ar,ar2 2,ar,ar (m)(m)也是模也是模mm的一简化剩余系的一简化剩余系. .证明：证明： 只需证明arl,ar2,ar(m) 互不同余,且都与m互素即可. 假设ariarj(mod m), 其中1i, j (m). 由于(a,m)=1, 故有rirj(mod m), 这与rl,r2,r(m)是模 m的一简化剩余系矛盾, 故

37、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 11 ( (欧拉定理欧拉定理) )设设mm2, 2, 且且( (a,m)=1,a,m)=1,则则: :a a (m)(m) 1(mod m).1(mod m).证明证明: : 设rl,r2,r(m)是模m的一简化剩余系, 则由定理10知, rl,r

38、2,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)的解. 注注：不同解是指互不同余的解.niiixaxf0)(2.4 一次同余式注意, 若x0是(1)的解, 则模m的剩余类x0, 即全部整数x0+km, k=0, 1, 2,中每一个都是

39、满足(1), 而x0是x0非负最小整数, 即是非负最小剩余.由定义可知, 要求(1)的解, 只要逐个把0,1, 2, ,(m-1)代人(1)中进行验算即可.但当m大时, 计算量往往太大.下面就来讨论一元一次同余式的解的问题.2.4 一次同余式定理定理 1111 设设( (a,m)=1, m0, a,m)=1, m0, 则则axax b(mod m) (2)b(mod m) (2) 恰有一解恰有一解, , 且且 x x baba (m)-1(m)-1(mod m)(mod m)证明证明 因为0,1,m-1是模m的一完全剩余系, (a,m)=1, 故0,a,2a,(m-1)a也是模m的一完全剩余系

40、, 所以其中恰有一整数, 设为ka, 满足ka b(mod m), 即k满足(2)，因而xk(mod m)是(2)的唯一解.由欧拉定理，立即可得xba (m)-1(mod m).2.4 一次同余式定理定理2 2 设设( (a,m)=d, m0, a,m)=d, m0, 则则axax b(mod m) (3)b(mod m) (3) 有解有解 iff d|biff d|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 3 设设

41、( (a,m)=d,m0,d|b,a,m)=d,m0,d|b,则则axax b(mod m) (4)b(mod m) (4) 恰有恰有d d个解个解. .证明证明 由d|b和定理2知(4)有解.显然, c为(4)的解 iff c也是:(a/d)x (b/d)(mod (m/d) (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 3 设设( (a,ma,m)=)=d,md,m0,d|b,0,d|b,则则 a

42、xax b b(mod m) (4)(mod m) (4) 恰有恰有d d个解个解. .证明证明( (续续) )： 这是因为对c+km/d, 令k=qd+r, 0rd, 代入c+km/d=c+(qd+r)m/dc+rm/d(mod m). 又若0ed, 0f0, n0, a an n 0(0(mod p), mod p), 则同余式则同余式f(x)f(x) 0(mod p) (1)0(mod p) (1) 最多有最多有n n个解个解证明证明 对n进行归纳. 当n=1时, 设一次同余式为a1x+a0 ( (mod p), p不能整除a1; 由于p不能整除a1; 故恰有一解. 现在, 假设定理对次

43、数为n-1(n2)的同余式真, 欲证(1)最多有n个解.当np时结论显然成立, 故可设np-1. 用反证法, 假设同余式(1)有n+1个解: x0,x1,xn, xixj(模)(mod p), 0ijn, 这将导致矛盾.niiixa1因为其中g(x)是首项系数为an的n-1次整数多项式,因此有但若k0, xk-x00(mod p), 故n-1次同余式g(x)0(mod p)有n个解, 与归纳假设矛盾.nkkkkxgxxxxaxfxf1000)()()()()()(mod0)()()()(00pxgxxxfxfkkk2.5 高次同余方程应用拉格朗日定理可得下面定理.定理定理2 2 设同余式设同余

44、式 的解的个数大于的解的个数大于 n, n, 其中其中p p是素数是素数, , a ak k是整数是整数,0,0kn, kn, 则则p|ap|ak k. .证明：证明： 若某些系数不被p整除, 令其最大下标为k, 则k n. k次同余式: 的解的个数大于k, 这与定理5矛盾.)(mod0)(0pxaxfnkkk)(mod00pxankkk2.5 高次同余方程定理定理3 3 对于任给素数对于任给素数p, p, 多项式多项式f(x)=(x-1)(x-2)f(x)=(x-1)(x-2)(x-p+1)-xx-p+1)-xp-1p-1+1+1的的所有系数被所有系数被p p整除整除. .证明证明 令g(x

45、)=(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个解. 故同余式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 高次同余方程下面对模 的同余方程做进一

46、步讨论。 容易看出，若 是同余方程 f(x) 0 (mod ) (1) 的解，则它必是方程 f(x) 0 (mod ) (2) 的解，因此，必有与 相应的方程(2)的某个解 ，使 此处， 是某个适当的整数。这提示我们：可以从方程(2)的解中去求方程(1)的解。于是，现在的问题是，对于方程(2)的每个解 ，是否必有方程(1)的解 与之对应？若有，如何去确定它？p0 xp1p0 x1x0110110),(modtpxxpxx0t1x0 x2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.6 原根本节围绕的是解高指数方程 xk a (mod m)

47、 主要利用的是欧拉定理 欧拉定理的不足： 26 1 (mod 7) 同时23 1 (mod 7) )(mod1)(mam2.6.1 指数与原根 对xk 1 (mod m) ，肯定有解，但最小解？定义定义1 1 设 ,m 1,(a, m) = 1，则使 a d 1 (mod m) (1)成立的最小的正整数d，称为a对模m的指数指数，记为ordm(a)，在不致误会的情况下，简记为ord(a)。指数也称为阶阶。Zma,2.6.1 指数与原根例如： ordm(1)=1, ord2(-1)=1, ordm(-1)=2(m2), ord17(3)=16注意：如果（a,m）1，则规定ordm(a)=0在谈到

48、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)观察： 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倍

49、所有的指数都是4的因数,4是什么？a1379ord10(a)14422.6.1 指数与原根定理定理1 1 指数的基本性质 a n 1 (mod m)的充要条件是的充要条件是ordm( (a)|n)|n 分析：设n= ordm(a)q+r, 0r ordm(a), q,rZ，则： a n a ord(a)q+r a r 1 (mod m)， 因为ordm(a) 最小，所以r=0。推论：推论： ordm(a)| (m)定义定义2 2 若ordm (a)= (m)称a是模m的原根原根（也写作元根） 如，3和5是模7的原根，3和7是模10的原根原根也可能没有，如模15、8没有原根2.6.1 指数与原根

50、例例 证明：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(mod 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 指数

51、与原根解：解： (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 1 指数的基本性质 若若a b (mod m)，(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)

52、| ordm(a) 所以ordm(a)=ordm(b)a-1a 1(mod m)，则则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) ord17(7)=ord17(5)=16例例 计算39、7模17的指数2.6.1 指数与原根定理定理1 1 指数的基本性质记记n n= ordm( (a) ) , ,则则a0, a1, , a n 1对模对模m两两不同余两两不同余。 分析：反证法.若0 i

53、 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 (m)是缩系，所以当1l0, 0, ordm( (a i)=)=s s ，则则 。 分析： (a i)s 1 (mod m) n= ordm(a) |is 则最小的s= 。注：注： 当（i,n）=1时，幂后指数不变，此时i的个数

54、为 （n）。 所以，有 （n）个与a 同指数, n= ordm(a) 。 所以，如果m有原根，则原根个数为 ( (m)。),( nins sniinin),(|),(snin|),(),(nin2.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/(3,3)=1ord7(16)=3/(4,3)=3a123456ord7(a)136362)3 (272.6.1 指数与原根例例 观察模7的所有缩系元素的

55、指数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的缩系中每个元素的指数的缩系中每个元素的指数方法1：依次计算幂（如前）方法2：首先找到一个原根，3(从2开始计算指数找原根)用此原根生成缩系：322, 336, 344, 35

56、5, 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 1 指数的基本性质若若n m ，则则ordn( (a)| )| ordm( (a) ) 分析： a ordm (a) 1 (mod m) = a ordm (a) 1 (mod n) 对于m=pe的情况特别有用若若(m, n) = 1，(a, mn) = 1，则则ordmn( (a)= )= ordm( (a),),or

57、dn( (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(3)= 6上面利用的是 ，利用直接因为(4，7)=1，所以ord28(3)=6,2=6。例例 计算3模28的指数ord28

58、(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 1 指数的基本性质 (ab, m) =1， ( (ordm( (a),),ordm( (b)=1)=1则则ordm( (ab)=)=ordm( (a) )ordm( (b) ) 分析：设a ordm (b) ordm (ab) a ordm (b) ordm (ab) b ordm (b) ordm (ab) (a b)

59、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(mod 23)，所以ord23(2)=11用以前的方法在计算3的幂，如不行在计算5的此时考虑只需找到一个ord23(

60、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的原根是存在?下面的定理不用证明，只需应用定理定理 若若p p是奇素数，则原根存在是奇素数，则原根存在. .定理定理 若若p p是奇素数，是奇素数，g