第二章 同余与同余式 同余的概念与基本性质 同余方程组的求解方法 线性同余方程、高次同余方程的求解 原根和指数 应用

第二章 同余与同余式 在日常生活中,有时我们注意的常常不是某些整数,而 是这些整数用某一个固定的整数去除所得到的余数. 第二章 同余与同余式 在日常生活中,有时我们注意的常常不是某些整数,而 是这些整数用某一个固定的整数去除所得到的余数. 例如本月2日是星期3,那么9日,16日,…都是星期3,这 是因为它们用7除后得到的余数都是2 在我国古代的干支纪年也是这样的,它是以60作为除 数的纪年法. 这样,在数学中就产生了同余的概念. 同余概念是Gauss在1800年前后创立的.

2.0 同余定义和基本性质 定义1 给定一正整数m, 若用m去除两个整数a和b所得 余数相同, 则称a与b为对模m同余, 记作ab(mod m); 若余数不同, 则称 a与b为对模m不同余。 ab(mod m) iff m|(a-b). a0(mod m) iff m| a. 性质: ①自反性: aa (mod m). ②对称性: 若ab(mod m), 则 ba(mod m). ③传递性: 若ab(mod m), bc(mod m), 则: ac(mod m). 可见, 同余关系是等价关系.

2.0同余式定义和基本性质 定理1 若ab(mod m), cd(mod m), 则: ① ax+cy  bx+dy(mod m), 其中x和y为任给整数. ② ac  bd(mod m). 1) 设a ≡ b (modm), c是任意整数.则 ac ≡bc(modm). 2) 设ai≡ bi (modm)(i =1,2,…,n, n>2),则 a1a2…an ≡b1b2…bn (modm). ③ an  bn(mod m), 其中 n＞0. ④ f(a) f(b)(mod m), 其中f(x)为任意的一个整系数多项式.

同余在算术里的两个应用： 应用1——检查因数的一些方法 一整数能被3(9)整除 iff 它的十进位数码的和能被 3(9)整除. 正整数a=an1000n+an-11000n-1+ … +a0 , 0≤ai<1000, 则 7(或11,或13)整除a iff 7(或11,或13)整除(a0 + a2 + …)-(a1 + a3 + …).

同余的算术应用1 * 正整数a能被9整除 iff 9整除a的十进制表示各数字 的和． 证明 若 , 则由 10i1(mod 9) (i=1,2,…,n) 和定理 1④可得: 注：因为10≡1(mod3)，同理, 一个整数能被3整除的必 要充分条件是它的10进位数码的和能被3整除.

同余的算术应用1 ** 正整数a能被7(或11，或13)整除 iff 7(或11，或13) 整 除a的定理十进制表示各数字的交错和 ． 证明：因为1000与-1对模7(或11，或13)同余， 由同余性质， (或mod11，或 mod13). 所以 ，结论得证。 

同余的算术应用2 ——弃九法 *证明了“弃九法”（弃九验算法）：把一个数的各位数字相加，直到和是一个一位数（和是9，要减去9得0），这个数就叫做原来数的弃九数．且一个数的弃九数与其模9的余数相等。 利用这种方法可以验算较大整数的加法、减法、乘法运算的结果是否正确，也可验算除法，但需转化成乘法。

弃九法 例1 验算 851+346=1198． 解： 先分别求出两个加数的弃九数与和的弃九数． 例1 验算 851+346=1198． 解： 先分别求出两个加数的弃九数与和的弃九数． 851、346的弃九数分别是5，4，1198的弃九数1． 两个加数的弃九数相加得4+5=9，弃掉9后是0，而题 目中和的弃九数是1，可以说这道题一定错误。 注：利用弃九法检验运算的结果是否正确时， 如果等号两边的九余数不相等，那么这个算式肯定不正确； 如果等号两边的九余数相等，那么还不能确定算式是否正确，因为九余数只有0，1，2，…，8九种情况，不同的数可能有相同的九余数。所以用弃九法检验运算的正确性，只是一种粗略的检验。

弃九法 例2 求证 1997×57≠113828. 证明 由于19971＋9＋9＋78 (mod 9) 例2 求证 1997×57≠113828. 证明 由于19971＋9＋9＋78 (mod 9) 57 5＋7  3(mod 9) 113828  l+1+3+8+2+8  5(mod 9) 但是, 8×3=24, 而24≠5(mod 9), 得证.

同余的应用举例 例1 已知2001年的国庆节是星期一，求2010年的国庆 节是星期几？ 例1 已知2001年的国庆节是星期一，求2010年的国庆 节是星期几？ 分析： 一星期有7天，要求2010年的国庆节是星期几，就要求从2001年到2010年的国庆节的总天数被7除的余数就行了。但在计算中，如果我们能充分利用同余性质，就可以不必算出这个总天数。 解： 2001年国庆节到2010年国庆节之间共有2个闰年 7个平年，即有“366×2+365×7”天。 ∵ 366×2≡2×2≡4（mod 7）， 365×7≡1×7≡0（mod 7），∴366×2+365×7≡2×2+1×7≡4+0≡4（mod 7） 答：2010年的国庆节是星期五。

同余的应用举例 例2 　判定21991 + 1 、 21998 + 1 是否为质数。 分析： 期望找到正整数m ,使 21991 + 1 ≡0 (mod m) , 即　 21991 ≡- 1 (mod m) . 解： 因为2 ≡- 1 (mod 3) ,所以, 21991 + 1 ≡ (-1)1991 + 1≡ (- 1) + 1 = 0 (mod 3) . 从而, 21991 + 1 为合数. 因为4 ≡- 1 (mod 5) ,所以, 21998 + 1 =4999+ 1 ≡ (-1)999 + 1 ≡ (-1)+ 1 = 0 (mod 5) . 从而, 21998 + 1 为合数.

2.0同余式定义和基本性质 定理 3 若ac=bc(mod m), (c,m)=d, 则 a  b(mod (m/d)) 证明 因为m|c(a-b), 于是(m/d)|((a-b)(c/d)), 又因为 (c,m)=d, 则有((c/d, m/d)=1, 因此 (m/d)|(a-b), 即: a  b(mod (m/d)). 显然, 由本定理可得如下推论. 推论 若 ac=bc(mod m), (c,m)=1,则: ab(mod m).

2.0同余式定义和基本性质 定理4 ① 若ab(mod m), 且d|m, 则: ab(mod m). ③ 若ab(mod m), 则 (a,m)=(b,m). ③ ab(mod mi), (1≤i≤n), iff ab (mod [m1,m2,…,mn]). 证明 只给出③的证明, ①和②读者完成. ③必要性:由①知,是成立的. 充分性: 若a  b(mod mi), 1≤i≤n, 则: mi|(a-b), 1≤i≤n, 即(a-b)是 m1,m2,…,mn的公倍数, 从而也是[m1,m2,…,mn] 的倍数, 因此: ab (mod [m1,m2,…,mn]).

p为素数 iff (p-l)!-1(mod p). 2.0同余式定义和基本性质 下面证明一个重要定理, 从应用和理论来说都有非常 大的意义. 尤其在理论上,它完全解决了判断给定的数 是否为素数的问题. 定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p).

定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p). 证明 必要性: 设p为一素数, 当p=2,3时, 结论显然成立. 现设p>3是一奇素数, S={2, 3, …, p-2}，aS. 因为 (a,p)=1, 存在整数m和n, 使am+pn=1, 于是 am1(mod p). 设b=m-pq, 即b是p除m的余数, 易知 b≠1, b≠p-1, 故 bS, 且 ab1(mod p). 可以证明 a≠b.

定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p). 假设 a=b, 则有(b-1)(b+1)0(mod p), 而 b≠l, b ≠p-1, 故(b-1)(b+1)0(mod p)不成立. 可见S中的数可分成(p-3)/2对, 每一对数a和b, 满 足 abl(mod p), 故得2·3…(p-2)  (mod p), 即可得 (p-1)! -1 (mod p).

定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p). 充分性: 若(p-1)! = -l (mod p), 则 p为素数. 假设p是合数, 令 p＝ab, a≠p. 由题设条件知, p|((p-1)!+l). 又因 a|p, 则有 a|((p-1)!+1). 但由于 a≤p-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是国际通用的图书或独立的出版物(除定期出版的期刊)代码。出版社可以通过ISBN清晰地辨认所有非期刊书籍。一个ISBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版的基础上没有内容上太大的变动，在出版时也不会得到新的ISBN号码。当平装本改为精装本出版时，原来相应的ISBN号码也应当收回。 国际标准图书编号问世后，很快得到推广，主要是因为它对出版商、书商的工作有很大的益处，体现在:国际标准书号是机读的编码，从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的作用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书业的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、采选、编目和流通程序都有促进作用;ISBN系统的引入也服务于书目信息的流动和使用，而且为一个国家的图书生产提供经济的书目控制;ISBN对图书市场更有效率，它能确定国际上出版的任何图书及其出版社。在书业中习惯称ISBN为库藏码(Stock Number)，就是因为其被普遍应用于书库管理。

同余关系及其在计算机领域的应用 10位数ISBN的结构 第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数字，大体上兼顾文种、国别和地区。0、1代表英语，使用这两个代码的国家有:澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、美国、津巴布韦等;2代表法语，法国、卢森堡以及比利时、加拿大和瑞士的法语区使用该代码;3代表德语，德国、奥地利和瑞士德语区使用该代码;4是日本出版物的代码;5是俄罗斯出版物的代码;7是中国出版物使用的代码。 第二组: 出版社代码。由国家或地区的ISBN中心设置并分给各个出版社。 第三组:书序码。该出版物代码，是出版者分配给每一个出版物的编号。 第四组:计算机校验码。校验码是ISBN号的最后一位数值，它能够校验出ISBN号是否正确。校验码只能是1位数，当为10时，记为罗马数字X。

同余关系及其在计算机领域的应用 左图是2007实行的新的ISBN标准，从10位升到13位，为了讲课方便，我们仍然用2007年以前的10位标准来讲述：

同余关系及其在计算机领域的应用

同余关系及其在计算机领域的应用

同余关系及其在计算机领域的应用 同余的应用2：验证信用卡的有效性 首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介绍国际上比较流行的Master卡，该卡标识码为16位，以51，52，53，54或者55开头. 比如：5548 3742 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，持卡人账号为427983069

同余关系及其在计算机领域的应用

同余关系及其在计算机领域的应用

xb1(mod m1), xb2(mod m2),…, xbk(mod mk) (1) 2.1 一次同余式组 本节介绍一次同余式组的解法及其应用举例． 在公元三世纪前,《孙子算经》里已提出了下面的同余 式组 xb1(mod m1), xb2(mod m2),…, xbk(mod mk) (1) 这种形式的问题, 并且很好地解决了它.《孙子算经》 里所提出的问题之一如下: “今有物不知其数, 三三数之剩二, 五五数之剩三, 七七 数之剩二. 问物几何？” “答日二十三.”

2.1 一次同余式组 把这个问题的提法用同余式的式子来表达，它可 表示成解同余式组 x2(mod 3), x3(mod 5), x2(mod 7) 其中x是所求物数. 关于同余式组: xa(mod 3), xb(mod 5), xb(mod 7) 的一般解为: x  70a+21b+15c (mod 105) 15:51:43

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

xb1(mod m1), xb2(mod m2) (1) 2.1 一次同余式组 定理1 一次同余式组 xb1(mod m1), xb2(mod m2) (1) 有解 iff (m1,m2)|(b1-b2), 且当(1)有解时对模[m1,m2]有唯一解. 证明： 设(1)有解x0, (m1,m2)=d, 则有: x0b1(mod m1), x0b2(mod m2) m1=dq1, m2=dq2 于是, x0-b1=dq1m’1, x0-b2=dq2m’2, 因此, d|(b1- b2). 若(m1,m2)|(b1-b2),则因xb1(mod m1)可表示为: x=b1+m1y, 代 入xb2(mod m2)得: m1y(b2-b1)(mod m2) (2) 因为(m1,m2)=d, d|(b2-b1), (2)有解, 设为y0, 且对模m2/d有唯 一解: yy0(mod (m2/d)), 15:51:43

xb1(mod m1), xb2(mod m2) (1) 2.1 一次同余式组 定理1 一次同余式组 xb1(mod m1), xb2(mod m2) (1) 有解 iff (m1,m2)|(b1-b2), 且当(1)有解时对模[m1,m2]有唯一解. 证明(续)：即 y=y0+km2/d, k=0,±1, ±2, …. 因此(1)的全部解为: x=b1+m1y0+m1m2k/d, k=0,±1, ±2, …. 这些解对模[m1,m2]是同余的, 故(1)的解对模[m1,m2]唯一. 15:51:43

2.1 一次同余式组 对于一次同余式组: xb1(mod m1), xb2(mod m2),…, xbk(mod mk), k>3的情形, 可先解前两个得xb’1(mod[m1,m2]), 再与xb3(mod m3)联立解出xb’3(mod[m1,m2,m3]). 如此 继续下去, 最后可得唯一解xb’k(mod[m1,m2 ,…,mk]). 注 若中间有一步出现无解, 则同余式组无解. 15:51:43

xb1M1’M1+b2M2’M2+…+bkMk’Mk(mod m)(2) 2.1 一次同余式组 定理2 (孙子定理)设m1, m2, …, mk是两两互素的k个正整 数, k＞=2, 并且m＝ m1 m2 … mk , m=miMi, 1≤i≤k, 则 同余式组(1)有唯一解 xb1M1’M1+b2M2’M2+…+bkMk’Mk(mod m)(2) 其中Mi’Mi1(mod mi), 1≤i≤k. 证明: (mi,mj)=1, i≠j, 即得(Mi,mi)=1. 对每一Mi, 存在M’i, 使 得 M’iMi  1(mod mi) (3) 另一方面, 当i≠j时, 则由(mi,mj)=1和m＝mjMj得到mi|Mj, 所 以有: bjM’jMj 0(mod mi) (4) 15:51:43

2.1 一次同余式组 由(3)和(4)有 即(2)是(1)的解. 若y也是(1)的解, 则得: xy(mod mi), 1≤i≤k 于是, mi|(x-y), 1≤i≤k. 由于ml, m2, …,mk两两互素. 故 m|(x-y), 即xy(mod m). 因此 是(1)的唯一解. 15:51:43

2.1 一次同余式组 应用孙子定理可以证明如下定理. 定理 3 设m1,m2,…,mk是两两互素的 k个正整数, m＝ m1m2…mk ,则同余式: f(x)0 (mod m) (1) 有解 iff 同余式组: f(x)0 (mod mi), 1≤i≤k (2) 的每个同余式有解, 且若用S表示(1)的解数, Si表示(2)的 解数, 则: S＝S1S2…Sk. 15:51:43

2.1一次同余式组 证明: 若x0是满足(1)的整数, 则由f(x0)0(mod m), 可得f(x0)0(mod mi), 1≤i≤k. 反之, 若xi满足(2), 1≤i≤k, 因为1≤i<j≤k, (mi,mj)=1, 由孙子定理, 有唯一的x0, 0≤x0<m, 满足x0 xi(mod mi), 1≤i≤k, 且f(x0) f(xi)0(mod mi), 1≤i≤k. 故f(x0)0(mod m).充要条件得证。 现在设(2)有Si个不同解是xaiji(mod mi), 0≤aiji< mi, 1≤i≤k , l≤ji≤Si, 对其中任一组a1ji, a2ji,…, akji, 由孙子定理可 得唯一的x, 0≤x<m, 是(1)的解, 且不同的组, 得到(1)的解也不 同, 故S＝S1S2…Sk. 15:51:43

x 1×3×462+1×5×385+1×4×330 + 1×10×210 6731 2111(mod 2310). 例1 韩信点兵:有兵一队, 若列成五行纵队, 则末行一人; 成六行 纵队, 则末行五人; 成七行纵队,则末行四人; 成十一行纵队,则末 行十人, 求兵数. 解： 设x是所求兵数, 则依题意: x1(mod 5), x 5(mod 6) x4(mod 7), x 10(mod 11) 令m1=5,m2=6,m3=7,m4=11,b1=l, b2=5, b3=4, b4=10. 于是m=m1m2m3m4=5×6×7 × 11=2310, M1=2310/5=462, M2=385, M3=330, M4=210. 有M’1M11(mod 5), 即1462 M’1 2M’1(mod 5) ,因此M’1=3. 同 理可求M’2=1, M’3=1, M’4=1. 故解为: x 1×3×462+1×5×385+1×4×330 + 1×10×210 6731 2111(mod 2310). 即 x=2111+2310k, k=0,1,2,…. 15:51:43

2.2 剩余类和剩余系 由于同余关系是等价关系, 因此对于给定的任一工整数m, 利用模m同余这个关系, 可将整数集划分成m个等价类, 由 于它是一些整数除m后的余数形成的, 所以称它是剩余类或 同余类.于是有: 定义1 设m是一给定的正整数, 若 [r] = {i: ir(mod m), iZ}, 0≤r≤m-1} 则称[r]是模m剩余类. 设a是任一整数, 则a＝mq+r, 0≤r<m, 故a恰包含在[r]中. 若a和b是两整数, 且在[r]中, 则a＝mq1+r, b=mq2+r, 故m|(a-b). 反之, m|(a-b), 则由同余定义即知a和b同在某一类[r]中, 0≤r<m.

2.2 剩余类和剩余系 定义2 在模m剩余类[0], [1], …,[m-1]中各取一数 ar[r], 0≤r≤m-1, 该m个数a0,a1,…,am-1称为模m的 一完全剩余系. 若令x={a0,a1,…,am-1}, 则称x是过模 m的完全剩余系. 由此定义得以下定理. 定理1 m个整数构成模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的一完全剩余系. 证明： 假设(ai+b)(aj+b)(mod m), 0≤i<j≤m-1, 则 m|(ai-aj), 由定理1和a0,a1,…,am-1是模m的一完 全剩余系,知假设不真,即a0+b,a1+b, …,am-1+b是两两 对模m不同余. 由定理1知, 它们是模m的一完全剩余系.

2.2 剩余类和剩余系 定理3 若a0,a1,…,am-1是模m的一完全剩余系, (b,m)=1. 则 ba0,ba1,…,bam-1也是模m的一完全剩 余系. 证明 仿定理2可证. 由定理2和3可证如下定理. 定理4 若a0,a1,…,am-1是模m的一完全剩余系b和c是任 意二整数且(b,m)=1, 则ba0+c, ba1+c, …,bam-1+c 也是模m的一完全剩余系.

2.2 剩余类和剩余系 定理5 设m1,m2是正整数, (m1,m2)=1, a0,a1,…,am1-1 , b0, b1, bm2-1分别是模m1和模m2的一完全剩余系, 则 S={m2ai+m1bj} 0≤i≤m1-1∧0≤j≤m2-1} 是模 m1m2 的一完全剩余系． 本定理也可简述如下: 设m1和m2是大于零的整数, (m1,m2)=1,x1和x2分别 是过模m1和m2的完全剩余系, 则m2x1+m1x2是过模 m1m2的完全剩余系.

2.2 剩余类和剩余系 证明： 显然S中有m1m2个整数, 由定理 1知, 只需证明它们 对模m1m2两两不同余即可. 假设m2ai1+m1bj1m2ai2+m1bj2(mod m1m2), 0≤i1, i2≤ m1- 1, 0 ≤j1,j2≤m2-1. 得，m2ai1m2ai2 (mod m1), m1bj1m1bj2(mod m2), 因为(m1, m2)=1, 故 ai1 ai2(mod m1), bj1 bj2(mod m2). 由于ai1,ai2是模ml的完全剩余系中的数, 故ai1=ai2. 同理 bj1=bj2. 因此, 若{ai1,ai2}和{bj1,bj2}不同,则 m2ai1+m1bj1≠m2ai2+m1bj2(mod m1m2). 因此 S是模m1m2的一完全剩余系.

2.2 剩余类和剩余系 1948年,乔拉(Chowla)等人证明了如下定理. 定理6 设a1,a2,…,an, b1, b2, bn分别是模n的一完全剩余 系, n>2, 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是一素数, k是一正整数, 则: (pk)=pk-1(p-1) 证明 因为小于或等于pk且与pk不互素的正整数恰是p的 各个倍数: 1·p,2·p,3·p,…,(pk-1)·p 显然共有pk-1个. 而小于或等于pk的正整数总共有pk个, 于是: (pk)= pk – pk-1= pk-1 (p-1).

2.2 剩余类和剩余系 定义4 若模m剩余类中的数与m互素, 则称它为与模m互素 的剩余类, 在与模m互素的所有剩余类中, 各取一数所组成 的集合, 称为模m的一个简化剩余系（缩系）. 由上面定义, 显然有下面二定理: 定理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互素即可. 假设ariarj(mod m), 其中1≤i, j ≤(m). 由于(a,m)=1, 故有rirj(mod m), 这与rl,r2,…,r(m)是模 m的一简化剩余系矛盾, 故ari≠arj(mod m), 即: arl,ar2,…,ar(m)两两互不同余. 假设p是m和某ari的公共素因数, 其中1≤i≤(m), 因p是素 数, 故p|a或p|ri. 因此, p是a和m的公因数, 或是ri和m的公 因数, 这与(a,m)=(ri,m)=l矛盾, ∴(ari,m)=l, l≤i＜(m) .即ari与m互素.

2.2 剩余类和剩余系 定理11 (欧拉定理)设m＞2, 且(a,m)=1,则: a(m)1(mod m). 证明: 设rl,r2,…,r(m)是模m的一简化剩余系, 则由定理10知, rl,r2,…,r(m)也是模m的一简化剩余系. 故 (arl)(ar2)…(ar(m))rlr2…r(m) (mod m). 即 a(m) rlr2…r(m) rlr2…r(m) (mod m). 由于(ri,m)=1, 1<i≤(m), 故(rlr2…r(m),m)=1. ∴ a(m)1(mod m).

2.2 剩余类和剩余系 注意到, 令m＝p, 且p是素数, 立刻得到如下定理. 定理12(费马定理) 若p是素数, 则: ap-1 1(mod m). 定理13 设m1,m2是正整数, (m1,m2)=l, rl,r2,…,r(m1)和 r’l,r’2,…,r’(m2)分别是模m1和模 m2的一简化剩余系, 则 S={m2ri+m1r’j}1≤i, j ≤(m)是模m1m2的一简化剩余系.

证明: 首先证明(m2ri+m1r’j,m1m2)=1, 其中1≤i≤(m1), 1≤j≤(m2), 定理13 设m1,m2是正整数, (m1,m2)=l, rl,r2,…,r(m1)和 r’l,r’2,…,r’(m2)分别是模m1和模 m2的一简化剩余系, 则 S={m2ri+m1r’j}1≤i, j ≤(m)是模m1m2的一简化剩余系. 证明: 首先证明(m2ri+m1r’j,m1m2)=1, 其中1≤i≤(m1), 1≤j≤(m2), 否则, 有素数p, p| m2ri+m1r’j, p|m1m2, 若p|m1， 则p|m2r2, 而p不能整除ri, 故 p|m2, 这(m1 ，m2)=1矛盾; 若p|m2, 可得出相同矛盾. 这便证明了(m1)(m2)个数(m2ri+m1rj)均与m2m1互素. 其次, 根据定理 5知 S中任两数对模 m2m1不同余. 因此, S是模 m2m1的一简化剩余系. 再次， m2m1的缩系中任一元必是S中的元素。

2.2 剩余类和剩余系 由该定理,立即可得如下推论: 推论（欧拉函数的积性性质） 若(m1,m2) =1, 则 (m1m2)= (m1)( m2). 定理 14 若 , 其中p1,p2,…, pn是 素数, l,2,…, n是正整数, 则: 证明： 由欧拉函数的积性性质 从定理7知, , 1≤i≤n. 因此:

2.2 剩余类和剩余系 例1. 求证6,9,12,15,18,21,24,27是模8的一完全剩余系, 而其中9,15,21,27是模8的一简化剩余系, 证明： (1)由于 66(mod 8), 91(mod 8), 124(mod 8), 157(mod 8),182(mod 8), 215(mod 8), 240(mod 8), 273(mod 8), 6,l,4,7,2,5,0,3和0,1,2,3,4,5,6,7只是次序不同,故 6,9,12,15,18, 21,24,27是模8的一完全剩余系. (2) 9,15,21,27和1,3,5,7只是次序不同,(8)=4, 因此 9,15, 21,27是模8的一简化剩余系.

2.3 不定方程 不定方程是指未知数个数多于方程个数，且对解有一定限制 (比如要求解为正整数等)的方程． 不定方程是数论中最古老的分支之一． 古希腊的丢番图早在公元3世纪就开始研究不定方程，因此 常称不定方程为丢番图方程． 中国是研究不定方程最早的国家，宋代数学家秦九韶的大衍 求一术将不定方程与同余理论联系起来． 研究不定方程要解决三个问题：①判断何时有解；②有解时 确定解的个数；③求出所有的解． 消元化简：在处理多元的不定方程当中，一般通过联立各个 方程，消去那些暂时不用或者限制条件较少的未知数，将多 元方程组转化成二元的整系数不定方程进行处理。

2.3 不定方程 定理1 如x0和y0为ax+by=c的一组解,则对任何整数t， x0+bt,y0-at也是ax+by=c的解。 定理2 方程ax+by=c有整数解 iff (a,b)|c。 证明: 假定存在x0和y0使ax0+by0=c,因 (a,b)|ax0,(a,b)|by0,所以(a,b)|c. 反之,假定(a,b)|c,则有某一m,使c=m(a,b).存在r和 s,使ar+bs=(a,b) 因此a(rm)+b(sm)=m(a,b)=c 从而x=rm,y=sm是一组解。

2.3 不定方程 定理3 假定ab≠0,(a,b)=1,且x0,y0是ax+by=c的一组解,则 ax+by=c的所有解可写为 x=x0+bt , y=y0-at, 其中t是整数。 证明： 由定理2,因为(a,b)=1,对任何c,有1|c,方程确实有解. 设r,s是ax+by=c的任意解.我们要证, r=x0+bt,s=y0-at必 对某一整数t成立. 由ax0+by0=c得 c-c=(ax0+by0)-(ar+bs) 即 a(x0-r)+b(y0-s)=0 由a|a(x0-r)和a|0,可得a|b(y0-s),由于(a,b)=1,所以a|y0-s。 即存在一个整数t,使at=y0-s。 ∴ s=y0-at,r=x0+bt。

定理3 假定ab≠0,(a,b)=1,且x0,y0是ax+by=c的一组解, 则ax+by=c的所有解可写为 x=x0+bt , y=y0-at, 其中t是整数。 注： 假定ab≠0。若(a,b)不整除c,则线性不定方程ax+by=c无解; 若(a,b)|c,则对a’x+b’y=c’(其中a’=a/(a,b),b’=b/(a,b),c’=c/(a,b)) 可找到一组解x=r, y=s,且ax+by=c的所有解可写为 x=r+b’t, y=s-a’t, 其中t是任意整数。

2.3 不定方程 定理4 不定方程 有整数解的充分必要条件是 。 证明： 必要性:设d=(a1,a2,…,an),显然d|N 定理4 不定方程 有整数解的充分必要条件是 。 证明： 必要性:设d=(a1,a2,…,an),显然d|N 充分性:设计一个算法求解。 算法如下： 求解算法(归纳法): 基础:二元一次方程有解。 归纳:令d2=(a1,a2), 则(d2,a3,a4,…,an)=d|N.由归纳假定,方 程d2t2+a3x3+…+anxn=N有解,设其一解为t2’,x3’,..,xn’.再考 虑a1x1+a2x2=d2t2’,用欧几里得算法可求得一解为x1’,x2’.则 a1x1’+a2x2’+a3x3’+…+anxn’=N

dn-2tn-2+an-1xn-1=dn-1tn-1 定理4 不定方程 有整数解的充分必要条件是 。 先求最后一个方程的一切解，然后代入倒数第二个， 继续求解，往上代入。 a1x1+a2x2=d2t2 d2t2+a3x3=d3t3 ………. dn-2tn-2+an-1xn-1=dn-1tn-1 dn-1tn-1+anxn=N

2.4 一次同余式 本节主要讨论一次同余式. 先给出同余式及其解的 概念. 定义1 设 , 其中, m是正整数, n>0, ai是整数, 0≤i≤n, 则 f(x)0(mod m) (1) 称为模 m同余式. 若 an≠0(mod m), 称n是(1)的次数. 若 x0满足 f(x)0(mod m), 则 xx0(mod m)称为(1)的解. 注：不同解是指互不同余的解.

2.4 一次同余式 注意, 若x0是(1)的解, 则模m的剩余类[x0], 即全部整 数x0+km, k=0, ±1, ±2,…中每一个都是满足(1), 而 x0是[x0]非负最小整数, 即是非负最小剩余. 由定义可知, 要求(1)的解, 只要逐个把0,1, 2, …,(m-1) 代人(1)中进行验算即可.但当m大时, 计算量往往太大. 下面就来讨论一元一次同余式的解的问题.

2.4 一次同余式 定理 11 设(a,m)=1, m>0, 则 axb(mod m) (2) 恰有一解, 且 xba(m)-1(mod m) 证明 因为0,1,…,m-1是模m的一完全剩余系, (a,m)=1, 故0,a,2a,…,(m-1)a也是模m的一完全剩余系, 所以其 中恰有一整数, 设为ka, 满足ka b(mod m), 即k满 足(2)，因而xk(mod m)是(2)的唯一解. 由欧拉定理，立即可得xba (m)-1(mod m).

2.4 一次同余式 定理2 设(a,m)=d, m>0, 则 axb(mod m) (3) 有解 iff 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 设(a,m)=d,m>0,d|b,则 axb(mod m) (4) 恰有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 设(a,m)=d,m>0,d|b,则 axb(mod m) (4) 恰有d个解. 证明(续)： 这是因为对c+km/d, 令k=qd+r, 0≤r<d, 代入 c+km/d=c+(qd+r)m/dc+rm/d(mod m). 又若0≤e<d, 0≤f<d, c+em/dc+fm/d(mod m),则有 e=f. 这就证明了(4)的任一解与(6)中某数模 m同余, 而(6)是 两两互不同余的d个数, 即知(4)恰有d个解.

2.4 一次同余式 一般地, 可用归纳法证明. 定理 4 设n≥1, m＞0, 同余式 (7) 有解 iff (a1,a2,…,an,m)|b. (8) 若(8)满足,则(7)的解数是:mn-1(a1,a2,…,an ,m). 证明 可参考有关书.

2.5 高次同余方程 由2.1节定理3可知，求解模m的同余方程可以 转化为对模 的同余方程的求解。本节将对模 的同余方程做进一步讨论。 首先给出关于模是素数的同余式的拉格朗日 (Lagrange)定理.

2.5 高次同余方程 定理1 设p为素数, f(x)= 是整系数多项式, 其中n>0, an0(mod p), 则同余式 f(x)0(mod p) (1) 最多有n个解． 证明 对n进行归纳. 当n=1时, 设一次同余式为a1x+a0 (mod p), p不能整除 a1; 由于p不能整除a1; 故恰有一解. 现在, 假设定理对次数为n-1(n≥2)的同余式真, 欲证(1) 最多有n个解.当n≥p时结论显然成立, 故可设n≤p-1. 用反 证法, 假设同余式(1)有n+1个解: x0,x1,…,xn, xi≠xj(模)(mod p), 0≤i＜j≤n, 这将导致矛盾.

因为 其中g(x)是首项系数为an的n-1次整数多项式,因此有 但若k＞0, xk-x0≠0(mod p), 故n-1次同余式g(x)0(mod p) 有n个解, 与归纳假设矛盾.

2.5 高次同余方程 应用拉格朗日定理可得下面定理. 定理2 设同余式 的解的个数大 于 n, 其中p是素数, ak是整数,0≤k≤n, 则p|ak. 证明： 若某些系数不被p整除, 令其最大下标为k, 则k≤n. 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-10(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)!+10(mod p), 即有(p-1)! -1(mod p). 这又一次证明了威尔逊定理.

2.5 高次同余方程 下面对模 的同余方程做进一步讨论。 容易看出，若 是同余方程 f(x)  0 (mod ) (1) 下面对模 的同余方程做进一步讨论。 容易看出，若 是同余方程 f(x)  0 (mod ) (1) 的解，则它必是方程 f(x)  0 (mod ) (2) 的解，因此，必有与 相应的方程(2)的某个解 ，使 此处， 是某个适当的整数。 这提示我们：可以从方程(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，称为a对模m的指数，记为 ordm(a)，在不致误会的情况下，简记为ord(a)。 指数也称为阶。

2.6.1 指数与原根 ordm(1)=1, ord2(-1)=1, ordm(-1)=2(m>2), ord17(3)=16 例如： 注意： 如果（a,m）>1，则规定ordm(a)=0 在谈到a对模m的指数时，总假定m>1，(a, m) = 1。 有的使用ordm (a)等同的符号是 m(a)， (a)，但ordm (a)更常用

2.6.1 指数与原根 11  1(mod 7) 23  1(mod 7) 36  1(mod 7) 模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的因数 a 1 2 3 4 5 6 ord7(a)

2.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是什么？ a 1 3 7 9 ord10(a) 4 2

2.6.1 指数与原根 定理1 指数的基本性质 ① a n  1 (mod m)的充要条件是ordm(a)|n 定理1 指数的基本性质 ① a n  1 (mod m)的充要条件是ordm(a)|n 分析：设n= ordm(a)q+r, 0≤r< ordm(a), q,r∈Z，则： a n  a ord(a)q+r  a r  1 (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)=6 5-1(mod 3) 521(mod 3) 5是模3的原根 5-1(mod 6) 521(mod 6) 5是模6的原根 55(mod 9) 52-2(mod 9) 53-1(mod 9) 544(mod 9) 552(mod 9) 561(mod 9) 5是模32原根 55(mod 18) 527(mod 18) 53-1(mod 18) 54-5(mod 18) 55-7(mod 18) 561(mod 18) 5是模2* 32原根

2.6.1 指数与原根 例 计算5模17的指数ord17(5)=？ 解： φ(17)=16,所以只需计算5的1、2、4、8、16次方 55(mod 17) 528(mod 17) 5413(mod 17) 5816-1(mod 17) 5161(mod 17) 所以ord17(5)=16，5是模17的原根。

2.6.1 指数与原根 定理1 指数的基本性质 ② 若a  b (mod m)，(a, m) = 1，则ordm(a)= ordm(b) 定理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)| 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)

例 计算39、7模17的指数 2.6.1 指数与原根 解： ord17(39)=ord17(5)=16 ∵7*5=1(mod 17)

2.6.1 指数与原根 定理1 指数的基本性质 ④记n= ordm(a) ,则a0, a1, , a n  1对模m两两不同余。 定理1 指数的基本性质 ④记n= ordm(a) ,则a0, a1, , a n  1对模m两两不同余。 分析：反证法.若0  i < j  n 1,使a i  a j (mod m)， 则由(a, m) = 1 得到 a j  i  1 (mod m)， 这与j-i<n = ordm(a) ,与指数的定义矛盾 所以定理成立. 特别的：g是原根<=>g0, g1, , g ψ(m) 1是模m的缩系 思路：g1,g2,,g (m) 这 (m)个数两两不同余，所以 一定组成缩系;另一方面,g1,g2,,g (m)是缩系，所以 当1≤l< (m)时，gl≡g (m) ，从而ordm(g)= (m)

2.6.1 指数与原根 a a2 a3 a4 a5 a6 6 3 2 4 5 1 观察 (模数m=7) 这是一个循环(循环多长?) 如果用2来做这个循环，就会出现2：→4 → 1 → 2 如果用5来做，5 → 4 → 6 → 2 → 3 → 1 → 5…… 观察指数:对于2， 2 → 4 → 6 对于5， 5 →(10)4 →(15)3 →(20)2 →(25)1 → …

二○一七年九月十一日 2.6.1 指数与原根 定理1 指数的基本性质 ⑤ 若a n  a l (mod m)，(a, m) = 1，则nl (mod ordm(a)) 分析：不妨设n≤l ，所以a l-n  1 (mod m) 所以ordm(a)| l-n 。 书定理4.1.4 96 © 2003-2004 Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary.

例 计算223456(mod 7) 2.6.1 指数与原根 解： ord7(2)=3， 23456(mod 3) 2

2.6.1 指数与原根 定理1 指数的基本性质 ⑥ 记n= ordm(a) ，i>0, ordm(a i)=s ，则 。 二○一七年九月十一日 2.6.1 指数与原根 定理1 指数的基本性质 ⑥ 记n= ordm(a) ，i>0, ordm(a i)=s ，则 。 分析： (a i)s  1 (mod m) <=> n= ordm(a) |is <=> <=> 则最小的s= 。 注： 当（i,n）=1时，幂后指数不变，此时i的个数为 （n）。 所以，有 （n）个与a 同指数, n= ordm(a) 。 所以，如果m有原根，则原根个数为 ( (m))。 书定理4.1.4 98 © 2003-2004 Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary.

2.6.1 指数与原根 例 观察模7的所有缩系元素的指数 ord7(2) =ord7(9)= ord = ord7(3) /(2, ord7(2) )=3 ord7(4)= ord7(2)/(ord7(2),2) =3/(2,3)=3 ord7(8)= 3/(3,3)=1 ord7(16)=3/(4,3)=3 a 1 2 3 4 5 6 ord7(a)

例 观察模7的所有缩系元素的指数 2.6.1 指数与原根 7的原根φ(φ(7))=φ(6)=2个，6有因子1、2、3、6 例 观察模7的所有缩系元素的指数 7的原根φ(φ(7))=φ(6)=2个，6有因子1、2、3、6 所以存在：3指数的φ(3)=2个 2指数的φ(2)=1个 1指数的φ(1)=1个 a 1 2 3 4 5 6 ord7(a)

例 求出模7的所有原根 2.6.1 指数与原根 解： 模7的原根的个数为 φ(φ(7))=φ(6)=2， 例 求出模7的所有原根 解： 模7的原根的个数为 φ(φ(7))=φ(6)=2， 由前例， 3是模7的原根,6的缩系元素有1，5。 所以35(mod 7)  3*22 12 5。 所以模7的两个原根：3和5。

2.6.1 指数与原根 例 计算7的缩系中每个元素的指数 方法1：依次计算幂（如前） 方法2： 例 计算7的缩系中每个元素的指数 方法1：依次计算幂（如前） 方法2： 首先找到一个原根，3(从2开始计算指数找原根) 用此原根生成缩系： 322, 336, 344, 355, 361 (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) 定理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),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 指数与原根 例 计算3模28的指数ord28(3)=？ 解：φ(28)= φ(4) φ(7)=2*6=12 本来需要计算幂为2、3、4、6 但是因为ord7(3)=6，ord4(3)=2， 所以6| ord28(3) 现在只需直接计算361(mod 28)，所以ord28(3)= 6 上面利用的是⑦ ，利用⑧直接 因为(4，7)=1，所以ord28(3)=[6,2]=6。

2.6.1 指数与原根 ord7(3)=6，所以6| ord49(3) 因为3681*9-17*9-2*3 -6(mod 49) 解： φ(49)= 49-7=42 ord7(3)=6，所以6| ord49(3) 因为3681*9-17*9-2*3 -6(mod 49) 所以ord49(3)= 42

2.6.1 指数与原根 定理1 指数的基本性质 ⑨ (ab, m) =1， (ordm(a),ordm(b))=1则ordm(ab)=ordm(a)ordm(b) 分析：设a ordm (b) ordm (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) 价值：简化求原根

计算模23的原根 2.6.1 指数与原根 解： φ(23)= 22，指数可能为1、2、11、22 直接计算:224, 2111(mod 23)，所以ord23(2)=11 用以前的方法在计算3的幂，如不行在计算5的…… 此时考虑只需找到一个ord23(a)=2，则ord23(2a)=22 而ord23(-1)=2 所以ord23(-2)=22，-2是原根，所以原根有φ(22)=10个 (-2)315,(-2)514,(-2)710,(-2)917,(-2)1319(mod 23) (-2)157,(-2)175,(-2)1920,(-2)2111 (mod 23) 所以模23的原根有：5,7,10,11,14,15,17,19,20,21。

2.6.2原根的存在条件 对于什么样的正整数m，模m的原根是存在? 下面的定理不用证明，只需应用 定理 若p是奇素数，则原根存在. 定理 若p是奇素数，g是模p的一个原根，则g或g+p是模 p2的原根，若g是模p2的原根，则g是模p的原根. 定理 模m有原根的必要条件是m = 2，4，p或2p，其中 p是奇素数，  1 .

2.6.3 模素数原根的计算技巧 思路：设ordp(a)=n，则n|p-1，若n<p-1则存在某个素 数pi|(p-1)/n 定理 设奇素数p，p-1= ，(pi是素数)，若a与p互 素，且 ， i=1,2,…,s 则a为p的原根。 思路：设ordp(a)=n，则n|p-1，若n<p-1则存在某个素 数pi|(p-1)/n 即： (p-1)/n= pi u 从而， 与条件矛盾，所以n=p-1。

练习 例 求模47的一个原根 解： 首先分解47-1=2*23 (a,47)=1,取a=2, 223 1 (mod 47)，失败 例 求模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)使 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 注： 类似于对数，所以这个解方程问题叫做离散对数问题。

a 1 2 3 4 5 6 ind3a 2.6.4 指数 a a2 a3 a4 a5 a6 6 3 2 4 5 1 7的指数表 填表规则 2.6.4 指数 a a2 a3 a4 a5 a6 6 3 2 4 5 1 7的指数表 填表规则 a所在行作乘法 ，ind a 所在行作加法 ind a为1时，对应的a为起始的那个原根 a 1 2 3 4 5 6 ind3a

例 解方程 x5  3 (mod 7) 练习 a 1 2 3 4 5 6 类似于解对数方程： ind3a 例 解方程 x5  3 (mod 7) 类似于解对数方程： 5ind3x ind33 1(mod 6) 为什么是6? ind3x 5(mod 6) 查表 x5(mod 7) 注意：模又恢复为7 当然也可以利用 ind5x 5ind5x ind53 5(mod 6) ind5x 1(mod 6) 直接 x5(mod 7)

练习 a 1 2 3 4 5 6 法一： 6-1  -1 (mod 7)，所以原方程化简为 ind3a 例 解方程 6*3x  5 (mod 7) 法一： 6-1  -1 (mod 7)，所以原方程化简为 3x  -5  2(mod 7)，所以xind33 ind32(mod 6) x2(mod 6) 仍然是6 法二：ind36+xind33 ind35(mod 6) 3+x5(mod 6) 指数模指数，底数模m

2.6.5 应用 三大难题之一：离散对数问题 gr  a (mod m)，已知g,a,m，求r困难。 当g、m、r已知时，用快速指数算法可比较容易 地求出a，但如果已知g,a,m ，求r则非常困难。 目前已知的最快的求离散对数算法其时间复杂度 为(m=p)： 所以当p很大时，该算法也是不可行的。

2.6.5 应用 三大难题之一：离散对数问题 EIGamal公钥密码体制 2.6.5 应用 三大难题之一：离散对数问题 gr  a (mod m)，已知g,a,m，求r困难 EIGamal公钥密码体制 (1)选取大素数p和p的一个原根a，(a,p)=1,1<a<p (2)选取整数d，1<d<p-1，计算b  ad (mod p)；p,a,b为公钥，d为私钥 (3)加密：对0<m<p，秘密的随机选取整数k,1<k<p-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 (mod p)

应用 密钥交换 Diffie-Hellman密钥交换 对称加密需要 素数p与其原根a为公开整数 设A,B希望交换密钥，则A选择随机数XA<p，计算YA  aXA(mod p)；类似的B选择随机数XB<p，计算YB  aXB(mod p)，X私有，Y公开 A计算KA(YB)XA(mod p)将其作为自身密钥 B计算KB(YA)XB(mod p)将其作为自身密钥 KA= KB实现了密钥的交换

应用 RSA定点攻击 ce ≡ me^2 ce^2 ≡me^3 ……（mod n）一旦 ce^t≡ c ≡ me（mod n） =〉 m ≡ ce^(t-1) （mod n） t不是很大时这种攻击可行 如何避免？如何让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，所以指数可能为1,2,5,10 从小到大依次试算 313, 329, 351(mod 11)，所以ord11(3)=5 根据这个结论可以推出 ord11(14)=5=ord11(4) 可以推出ord11(-3)= ord11(-1)* ord11(3)=10 所以-38是原根，原根一共φ(10)=4个 所以823，8329 726， 87221212， 89227277，即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)=ordm(a)ordm(b) 奇素数p，p-1=

练习 求模41的原根情况 φ(11)=40,现在只要考察x8, x20 从2开始,因为 2810, 2201(mod 41); 所以6是模41的原根

练习 求模41的原根情况 因为:6236, 63-3011, 6425, 65-5527(mod 41);

练习 求模41的原根情况 所以:指数为1的元素有φ(1)=1个,是1; 指数为2的元素有φ(2)=1个,是62040 (mod 41); 指数为5的元素有φ(5)=4个,是10，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

总结 a a2 a3 a4 a5 a6 3 2 6 4 5 1 指数的价值： 原根的价值 幂化简 生成元：生成缩系所有元素 <g>,{gd} d遍历φ(p)的缩系(φ(φ(p))个)，gd遍历模p的原根 g是原根的时候幂与(计算幂后的)值形成置换

总结 原根的价值之二 可以推出其余所有缩系元素的指数 ordm(ai)=ordm(a)/(ordm(a),i) 可以根据幂对缩系元素按指数分类 a a2 a3 a4 a5 a6 2 4 8 5 10 9 a7 a8 a9 a10 7 3 6 1

练习 首先计算φ(11)=10，所以指数可能为1,2,5,10 k=1时，有φ(1)=1个； k=2时，有φ(2)=1个 计算同余方程xk  1 (mod 11)的解的个数 首先计算φ(11)=10，所以指数可能为1,2,5,10 k=1时，有φ(1)=1个； k=2时，有φ(2)=1个 k=5时，有φ(5)=4个； k=10时，有φ(10)=4个 考虑不周，k=3,4等其他数时呢 x  1 (mod 11)是k等于任何值的解

练习 关键在于指数可能可以化简 指数可取1,2,5,10, 指数为1时，有1个解，此时k可取1的倍数，即1-10任意数 计算同余方程xk  1 (mod 11)的解的个数 关键在于指数可能可以化简 指数可取1,2,5,10, 指数为1时，有1个解，此时k可取1的倍数，即1-10任意数 指数为2时，有1个解，此时k取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)各有哪些解？ 先找出每个指数对应的解，要计算指数先找出原根 原根都是试找的，先看2 所以生成缩系中的其它元素 224, 238, 245, 2510, 269 (mod 11) 277, 283, 296, 2101 (mod 11) 所以原根有：2、8、7、6（幂与10互质） 指数为5的有：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时有解x1(mod 11) k=2、4、6、8时有解x1(mod 11)和x10(mod 11) k=5时有解x1,3,4,5,9(mod 11) K=10时有解x1,2,3,4,5,6,7,8,9,10(mod 11)

2.6.6 初等数论在计算机科学技术中的几个应用 费马小定理的应用 费马小定理 设p是素数, a与p互素, 则 ap-1≡1(mod p). 2.6.6 初等数论在计算机科学技术中的几个应用 费马小定理的应用 费马小定理 设p是素数, a与p互素, 则 ap-1≡1(mod p). 另一种形式是, 设p是素数, 则对任意的整数a, ap≡a(mod p). 费马小定理提供了一种不用因子分解就能断定一 个数是合数的新途径. 例如, 291≡4 (mod 9), 可以断定9是合数.

2.6.6 初等数论在计算机科学技术中的几个应用 产生均匀伪随机数的方法 随机数： 随机变量的观察值 2.6.6 初等数论在计算机科学技术中的几个应用 产生均匀伪随机数的方法 随机数与伪随机数 线性同余法与乘同余法 随机数： 随机变量的观察值 伪随机数： 用计算机随机函数所产生的“随机 数”并不随机，是伪随机数。 (0,1)上的均匀分布U(0,1): a(0<a<1), P{0<X≤a}=a

2.6.6 初等数论在计算机科学技术中的几个应用 线性同余法 2.6.6 初等数论在计算机科学技术中的几个应用 线性同余法 选择4个非负整数: 模数m, 乘数a, 常数c和种子数x0, 其中2≤a<m, 0≤c<m, 0≤x0<m, 用递推公式产生伪随机数序列: xn=(axn1+c) mod m, 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 初等数论在计算机科学技术中的几个应用 乘同余法: xn=axn1 mod m, n=1,2,…. 2.6.6 初等数论在计算机科学技术中的几个应用 乘同余法: c=0(x0≠0)的线性同余法, 即 xn=axn1 mod m, n=1,2,…. 最常用的均匀伪随机数发生器:m=2311, a=75的乘同余法,它的周期是2312.

作业 P34 2.5 补充练习： 1. 解同余方程：x12 ≡ 16 (mod 17)。 2. 设m ≥ 3，g1和g2都是模m的原根，则g = g1g2不是模m的原根。