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

Presentation on theme: "第二章 同余与同余式 同余的概念与基本性质 同余方程组的求解方法 线性同余方程、高次同余方程的求解 原根和指数 应用."— Presentation transcript:

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

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

3 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). 可见, 同余关系是等价关系.

4 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)为任意的一个整系数多项式.

5 同余在算术里的两个应用： 应用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 + …).

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

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

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

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

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

11 同余的应用举例 例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年的国庆节是星期五。

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

13 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).

14 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]).

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

16 定理 (威尔逊定理) 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.

17 定理 (威尔逊定理) 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).

18 定理 (威尔逊定理) 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为素数.

19 同余关系及其在计算机领域的应用 同余的应用1：国际图书标准(ISBN编码)
ISBN是international standard of book number 的缩写，即国际标准图书编号。ISBN是国际通用的图书或独立的出版物(除定期出版的期刊)代码。出版社可以通过ISBN清晰地辨认所有非期刊书籍。一个ISBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版的基础上没有内容上太大的变动，在出版时也不会得到新的ISBN号码。当平装本改为精装本出版时，原来相应的ISBN号码也应当收回。 国际标准图书编号问世后，很快得到推广，主要是因为它对出版商、书商的工作有很大的益处，体现在:国际标准书号是机读的编码，从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的作用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书业的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、采选、编目和流通程序都有促进作用;ISBN系统的引入也服务于书目信息的流动和使用，而且为一个国家的图书生产提供经济的书目控制;ISBN对图书市场更有效率，它能确定国际上出版的任何图书及其出版社。在书业中习惯称ISBN为库藏码(Stock Number)，就是因为其被普遍应用于书库管理。

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

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

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

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

24 同余关系及其在计算机领域的应用 同余的应用2：验证信用卡的有效性
首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介绍国际上比较流行的Master卡，该卡标识码为16位，以51，52，53，54或者55开头. 比如： 在Master卡中，具备如下性质： 1.如果第2位为1，则第2到3位表示银行号。 2.如果第2位为2，则第2到4位表示银行号。 3.如果第2位为3，则第2到5位表示银行号。 4.如果第2位为其他值，则第2到6位表示银行号。 银行号后面直到第15位为持卡人账号，最后一位为校验位。比如刚才的例子中，第2位为5，则银行号为54837，持卡人账号为

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

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

27 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) 这种形式的问题, 并且很好地解决了它.《孙子算经》 里所提出的问题之一如下: “今有物不知其数, 三三数之剩二, 五五数之剩三, 七七 数之剩二. 问物几何？” “答日二十三.”

28 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

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

30 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

31 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

32 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

33 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

34 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

35 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

36 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

37 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× ×10×210 6731 2111(mod 2310). 即 x= k, k=0,1,2,…. 15:51:43

38 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.

39 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的最小完全正剩余系．

40 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的一完全剩余系.

41 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的一完全剩余系.

42 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的完全剩余系.

43 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的一完全剩余系.

44 2.2 剩余类和剩余系 1948年,乔拉(Chowla)等人证明了如下定理.
定理6 设a1,a2,…,an, b1, b2, bn分别是模n的一完全剩余 系, n>2, a1b1,a2b2,…,anbn 则不是模n的一完全剩余 系. 证明 读者可参见有关书籍的证明．

45 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.

46 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).

47 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 不同余.

48 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互素.

49 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).

50 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的一简化剩余系.

51 证明: 首先证明(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中的元素。

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

53 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的一简化剩余系.

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

55 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是一组解。

56 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。

57 定理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是任意整数。

58 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

59 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

60 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)的解. 注：不同解是指互不同余的解.

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

62 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).

63 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)有解.

64 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

65 定理 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个解.

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

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

68 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, 这将导致矛盾.

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

70 2.5 高次同余方程 应用拉格朗日定理可得下面定理. 定理2 设同余式 的解的个数大 于 n, 其中p是素数, ak是整数,0≤k≤n, 则p|ak. 证明： 若某些系数不被p整除, 令其最大下标为k, 则k≤n. k 次同余式: 的解的个数大于k, 这与定理5矛盾.

71 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). 这又一次证明了威尔逊定理.

72 2.5 高次同余方程 下面对模 的同余方程做进一步讨论。 容易看出，若 是同余方程 f(x)  0 (mod ) (1)
下面对模 的同余方程做进一步讨论。 容易看出，若 是同余方程 f(x)  0 (mod ) (1) 的解，则它必是方程 f(x)  0 (mod ) (2) 的解，因此，必有与 相应的方程(2)的某个解 ，使 此处， 是某个适当的整数。 这提示我们：可以从方程(2)的解中去求方程(1)的解。 于是，现在的问题是，对于方程(2)的每个解 ，是否必有方 程(1)的解 与之对应？若有，如何去确定它？

73 2.5 高次同余方程

74 2.5 高次同余方程

75 2.5 高次同余方程

76 2.5 高次同余方程

77 2.5 高次同余方程

78

79

80

81

82

83

84 2.6 原根 本节围绕的是解高指数方程 xk  a (mod m) 主要利用的是欧拉定理 欧拉定理的不足：
26 1 (mod 7) 同时23 1 (mod 7)

85 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)。 指数也称为阶。

86 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)更常用

87 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)

88 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

89 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没有原根

90 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原根

91 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的原根。

92 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)

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

94 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)

95 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 → …

96 二○一七年九月十一日 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 © Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary.

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

98 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 © Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary.

99 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)

100 例 观察模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)

101 例 求出模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。

102 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。

103 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

104 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。

105 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

106 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) 价值：简化求原根

107 计算模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。

108 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 .

109 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。

110 练习 例 求模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的一个原根

111 2.6.4 指标 定义1 设m是大于1的整数，g是其一个原根，(a,m)=1， 则存在唯一整数r (0 ≤ r ≤ φ(m)－1)使
指标 定义1 设m是大于1的整数，g是其一个原根，(a,m)=1， 则存在唯一整数r (0 ≤ r ≤ φ(m)－1)使 gr  a (mod m) 则r叫做以g为底的a对模m的一个指标，记为r=indga 注： 类似于对数，所以这个解方程问题叫做离散对数问题。

112 a 1 2 3 4 5 6 ind3a 2.6.4 指数 a a2 a3 a4 a5 a6 6 3 2 4 5 1 7的指数表 填表规则
指数 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

113 例 解方程 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)

114 练习 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

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

116 2.6.5 应用 三大难题之一：离散对数问题 EIGamal公钥密码体制
应用 三大难题之一：离散对数问题 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)

117 应用 密钥交换 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实现了密钥的交换

118 应用 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应有大素因子强素数

119 总结 原根 缩系中指数与欧拉函数相等的数 模m有原根的必要条件是m = 2，4，p或2p，其中p是奇素数，  1 指数：
ak  1 (mod m)成立的最小正整数k,写作ordm(a) 或m(a) 若指数与欧拉函数不等，指数也整除欧拉函数 等指数：同余、互逆数的指数相同 如何计算指数？ 幂从小到大取欧拉函数的因数试算，直到≡1 如何计算原根 计算出的指数等于欧拉函数

120 练习 计算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是原根

121 总结 寻找一个原根的技巧: 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=

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

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

124 练习 求模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

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

126 总结 原根的价值之二 可以推出其余所有缩系元素的指数 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

127 练习 首先计算φ(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等于任何值的解

128 练习 关键在于指数可能可以化简 指数可取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个解

129 练习 进一步：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

130 练习 进一步：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)

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

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

133 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,…

134 2.6.6 初等数论在计算机科学技术中的几个应用 乘同余法: xn=axn1 mod m, n=1,2,….
初等数论在计算机科学技术中的几个应用 乘同余法: c=0(x0≠0)的线性同余法, 即 xn=axn1 mod m, n=1,2,…. 最常用的均匀伪随机数发生器:m=2311, a=75的乘同余法,它的周期是2312.

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