《离散数学4课件幻灯片》由会员分享，可在线阅读，更多相关《离散数学4课件幻灯片（38页珍藏版）》请在金锄头文库上搜索。
1、11.3 同余,同余 模算术运算 模m等价类,1,同余,2,定义11.5 设m是正整数, a和b是整数. 如果m|ab, 则称a模 m同余于b, 或a与b模m同余, 记作ab(mod m). 如果a与b模 m不同余, 则记作a b(mod m). 例如, 153(mod 4), 160(mod 4), 14 2(mod 4), 15 16(mod 4). 下述两条都是a与b模m同余的充分必要条件: (1) a mod m = b mod m. (2) a=b+km, 其中k是整数.,同余(续),性质11.3.1 同余关系是等价关系, 即同余关系具有 自反性. aa(mod m) 传递性. ab
2、(mod m)bc(mod m) ac(mod m). 对称性. ab(mod m) ba(mod m). 缩写 a1a2ak (mod m). 性质11.3.2 模算术运算 若ab(mod m), cd(mod m), 则 acbd(mod m), acbd(mod m), akbk(mod m), 其中k是非负整数. 性质11.3.3 设d1, d | m, 则ab(mod m) ab(mod d). 性质11.3.4 设d1, 则ab(mod m) dadb(mod dm). 性质11.3.5 设c,m互素, 则ab(mod m) cacb(mod m).,3,模m等价类,模m等价类:
3、在模m同余关系下的等价类. am, 简记作a. Zm: Z在模m同余关系下的商集 在Zm上定义加法和乘法如下: a, b, a+b=a+b, ab=ab.,4,例1 写出Z4的全部元素以及Z4上的加法表和乘法表.,解 Z4=0,1,2,3, 其中i=4k+i |kZ, i=0,1,2,3.,0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2,0 0 0 0 0 1 2 3 0 2 0 2 0 3 2 1,实例,例2 3455的个位数是多少?,5,解 设3455的个位数为x,则3455x(mod10).,由341(mod 10), 有 3455=34113+3337(mod 10),
4、 故3455的个位数是7.,实例,例3(续) 例如, 中华人民共和国成立日1949年10月1日, C=19, X=49, M=8, d=1, 是星期六. 中国人民抗日战争胜利日1945年8月15日, C=19, X=45, M=6, d=15, 是星期三.,6,11.4 一次同余方程,11.4.1 一次同余方程 模m逆 11.4.2 中国剩余定理 11.4.3 大整数算术运算,7,一次同余方程,定理11.8 方程axc(mod m)有解的充要条件是gcd(a,m)|c. 证 充分性. 记d=gcd(a,m), a =da1, m =dm1, c =dc1, 其中a1与 m1互素. 由定理11.
5、7, 存在x1和y1使得a1x1+m1y1=1. 令x=c1x1, y=c1y1, 得a1x+m1y=c1. 等式两边同乘d, 得ax+my=c. 所以, axc(mod m). 必要性. 设x是方程的解, 则存在y使得ax+my=c. 由性质 11.1.1, 有d | c.,8,一次同余方程: axc(mod m), 其中m0. 一次同余方程的解: 使方程成立的整数 例如, 2x0(mod 4)的解为x0(mod 2), 2x1(mod 4)无解,实例,例1 解一次同余方程 6x3(mod 9). 解 gcd(6,9)=3 | 3, 方程有解. 取模9等价类的代表x= 4, 3, 2, 1,
6、 0, 1, 2, 3, 4, 检查它 们是否是方程的解, 计算结果如下: 6(4)6(1)623(mod 9), 6(3)60630(mod 9), 6(2)61646(mod 9), 得方程的解 x= 4, 1, 2(mod 9), 方程的最小正整数解是2.,9,模m逆,定理11.9 (1) a的模m逆存在的充要条件是a与m互素. (2)设a与m互素, 则在模m下a的模m逆是惟一的. 证 (1) 这是定理11.8的直接推论. (2) 设ab11(mod m), ab21(mod m). 得a(b1b2)0(mod m). 由a与m互素, b1b20(mod m), 得证b1b2(mod m
7、).,10,定义11.6 如果ab1(mod m), 则称b是a的模m逆, 记作a1(mod m)或a1. a1(mod m)是方程ax1(mod m)的解.,实例,例2 求5的模7逆.,11,解 5与7互素, 故5的模7逆存在.,方法1. 解方程5x1(mod7).,检查x= 3,2,1,0,1,2,3, 得到 513(mod7).,方法2. 做辗转相除法, 求得整数b,k使得 5b+7k=1, 则b是 5的模7逆.,计算如下: 7=5+2, 5=22+1. 回代 1=522=52(75)= 3527, 得 5 13(mod7).,中国剩余定理(孙子定理),定理11.10 (中国剩余定理)
8、设正整数m1, m2,mk两两互素, 则一次同余方程组 xai(mod mi), i=1,2, ,k 有整数解, 并且在模m=m1m2mk下解是惟一的, 即任意两 个解都是模m同余的.,12,孙子算经 “物不知数”问题: 今有物, 不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何? x2(mod 3) x3(mod 5) x2(mod 7),中国剩余定理的证明,13,假设 则 x=x1+x2+xk是所求的解. 令Mi=m/mi, i=1, 2, k. 设xi=Mi yi, 应该有 Mi yiai(mod mi). 因为mi与所有的mj(ji)互素, mi与Mi 也互素, 所
9、以Mi有模 mi逆, 设为Mi1. 取yi=ai Mi1, 则xi=Miyi=ai Mi 1Mi 满足要求. 得方程组的解 x= a1M11M1+ a2M21M2+ +akMk 1Mk,中国剩余定理的证明(续),最后, 证明惟一性. 设同余方程组有两个解c1和c2, 则对每一 个i, c1和c2模mi同余, 即mi|c1c2. 又m1, m2, , mk两两互素, 故有m|c1c2, 即c1和c2模m同余.,14,一次同余方程组的求解步骤,15,设正整数m1, m2,mk两两互素, 一次同余方程组 xai(mod mi), i=1,2, ,k (1) 计算m= m1m2mk (2) 计算Mi=
10、m/mi= m1mi 1mi+1mk, i=1, 2, k (3) 计算Mi1(mod mi), i=1, 2, k (4) 计算xa1M11M1+ a2M21M2+ +akMk1Mk(mod m),实例,例3 解“物不知数”问题, 即求下述方程组的正整数解: x2(mod 3), x3(mod 5), x2(mod 7), 解 这里m1=3, m2=5, m3=7, m=105. M1=57=35, M12(mod 3), M11=2. M2=37=21, M21(mod 5), M21=1. M3=35=15, M31(mod 7), M31=1. x2235+3121+211523323
11、(mod 105). 解为105k+23, k=0,1,2,. 最小正整数解是23.,16,大整数算术运算,设m1,m2,mk大于1且两两互素, m=m1m2mk. 对任意的 0xm, 令xi=x mod mi, i=1,k. 把(x1,x2,xk)叫作x关于 模m1,mk的模表示, 简称x的模表示, 记作x=(x1,x2,xk). 模表示运算 设x=(x1,x2,xk), y=(y1,y2,yk), 则有 x+y=(x1+y1)mod m1, (x2+y2)mod m2, , (xk+yk)mod mk), xy=(x1y1)mod m1, (x2y2)mod m2, , (xkyk)mod
12、 mk), xy=(x1y1mod m1, x2y2mod m2, , xkykmod mk).,17,实例,例4 取m1=9, m2=7, m3=5, m=975=315, 可以通过关于 模9, 7, 5的算术运算实现315以内的算术运算. 设x=20, y=13, 有 x=(2, 6, 0), y=(4, 6, 3), x+y=(2+4)mod 9, (6+6)mod 7, (0+3)mod 5)=(6, 5, 3), xy=(24)mod 9, (66)mod 7, (03)mod 5)=(7, 0, 2), xy=(24mod 9, 66mod 7, 03mod 5)=(8, 1, 0
13、). 求下述方程组的最小正整数解: z6(mod 9) z7(mod 9) z8(mod 9) z5(mod 7) z0(mod 7) z1(mod 7) z3(mod 5) z2(mod 5) z0(mod 5),18,实例(续),计算如下: M1=35, M11(mod 9), M11= 1, M2=45, M23(mod 7), M21=5, M3=63, M33(mod 5), M31=2, 得 x+y=(6(1)35+5545+3263) mod 315=33. xy=(7(1)35+0545+2263) mod 315=7, xy=(8(1)35+1545+0263) mod 31
14、5=260.,19,大整数算术运算(续),20,取mi= 1,记A= , 设 x=atAt+at1At1+a1A+a0, 其中0aj71044. 这就可 以用上述方法计算结果不超过71044的整数加、减、乘 .,11.5 欧拉定理和费马小定理,欧拉函数 欧拉定理 费马小定理,21,欧拉(Eular)定理,欧拉函数(n): 0, 1, n1中与n互素的数的个数 例如 (1)=(2)=1,(3)=(4)=2. 当n为素数时(n)=n1; 当n为合数时(n)n1. 定理11.11(欧拉定理) 设a与n互素, 则 a(n)1(mod n).,22,欧拉定理的证明,23,证 设r1, r2, r(n)是
15、0, 1, n1中与n互素的(n)个数. 由于a与n互素, 对每一个1i(n), ari也与n互素, 故存 在1(i)(n) 使得 arir(i)(mod n). 是1,2,(n) 上的映射. 要证 是一个单射. a的模n逆a1存在, a1也与n互素. 假设ij, (i)= (j), 则有 ariarj(mod n). 两边同乘a1, 得rirj(mod n), 矛盾. 得证 是1, 2,(n)上的单射, 当然也是1, 2,(n)上的 双射. 从而,有 而 与n互素, 故a(n)1(mod n).,费马(Fermat)小定理,定理11.12(费马小定理) 设p是素数, a与p互素, 则 ap-11(
