离散数学-113-5同余.ppt

《离散数学-113-5同余.ppt》由会员分享，可在线阅读，更多相关《离散数学-113-5同余.ppt（25页珍藏版）》请在三一办公上搜索。

1、课件,1,11.3 同余,同余模算术运算模m等价类,课件,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是整数.,课件,3,同余(续),同余关系是等价关系,即同余关系具有 自反性.aa(mod m)传递性.ab(mod m)bc(mod m)ac(mod m).

2、对称性.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是非负整数.设d1,d|m,则ab(mod m)ab(mod d).设d1,则ab(mod m)dadb(mod dm).设c,m互素,则ab(mod m)cacb(mod m).,课件,4,模m等价类,模m等价类:在模m同余关系下的等价类.am,简记作a.Zm:Z在模m同余关系下的商集在Zm上定义加法和乘法如下:a,b,a+b=a+b,ab=ab.,例1 写出Z

3、4的全部元素以及Z4上的加法表和乘法表.,解 Z4=0,1,2,3,其中i=4k+i|kZ,i=0,1,2,3.,0 1 2 31 2 3 02 3 0 13 0 1 2,0 0 0 00 1 2 30 2 0 20 3 2 1,课件,5,实例,例2 3455的个位数是多少?,解 设3455的个位数为x,则3455x(mod10).,由341(mod 10),有 3455=34113+3337(mod 10),故3455的个位数是7.,课件,6,实例,例3(续)例如,中华人民共和国成立日1949年10月1日,C=19,X=49,M=8,d=1,是星期六.中国人民抗日战争胜利日1945年8月15

4、日,C=19,X=45,M=6,d=15,是星期三.,课件,7,11.4 一次同余方程,11.4.1 一次同余方程模m逆11.4.2 中国剩余定理11.4.3 大整数算术运算,课件,8,一次同余方程,定理11.9 方程axc(mod m)有解的充要条件是gcd(a,m)|c.证 充分性.记d=gcd(a,m),a=da1,m=dm1,c=dc1,其中a1与m1互素.由定理11.8,存在x1和y1使得a1x1+m1y1=1.令x=c1x1,y=c1y1,得a1x+m1y=c1.等式两边同乘d,得ax+my=c.所以,axc(mod m).必要性.设x是方程的解,则存在y使得ax+my=c.由性质

5、11.1.1,有d|c.,一次同余方程:axc(mod m),其中m0.一次同余方程的解:使方程成立的整数例如,2x0(mod 4)的解为x0(mod 2),2x1(mod 4)无解,课件,9,实例,例1 解一次同余方程 6x3(mod 9).解 gcd(6,9)=3|3,方程有解.取模9等价类的代表x=4,3,2,1,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.,课件,10,模m逆,定理11.10(1)a的模

6、m逆存在的充要条件是a与m互素.(2)设a与m互素,则在模m下a的模m逆是惟一的.证(1)这是定理11.9的直接推论.(2)设ab11(mod m),ab21(mod m).得a(b1b2)0(mod m).由a与m互素,b1b20(mod m),得证b1b2(mod m).,定义11.6 如果ab1(mod m),则称b是a的模m逆,记作a1(mod m)或a1.a1(mod m)是方程ax1(mod m)的解.,课件,11,实例,例2 求5的模7逆.,解 5与7互素,故5的模7逆存在.,方法1.解方程5x1(mod7).,检查x=3,2,1,0,1,2,3,得到 513(mod7).,方法

7、2.做辗转相除法,求得整数b,k使得 5b+7k=1,则b是5的模7逆.,计算如下:7=5+2,5=22+1.回代 1=522=52(75)=3527,得 5 13(mod7).,课件,12,实例,例2(续),方法3.直接观察,53=15,15 1(mod 7),得 513(mod7).,课件,13,中国剩余定理(孙子定理),定理11.11(中国剩余定理)设正整数m1,m2,mk两两互素,则一次同余方程组 xai(mod mi),i=1,2,k有整数解,并且在模m=m1m2mk下解是惟一的,即任意两个解都是模m同余的.,孙子算经“物不知数”问题:今有物,不知其数,三三数之剩二,五五数之剩三,七

8、七数之剩二,问物几何?x2(mod 3)x3(mod 5)x2(mod 7),课件,14,中国剩余定理的证明,假设则 x=x1+x2+xk是所求的解.令Mi=m/mi,i=1,2,k.设xi=Mi yi,应该有 Mi yiai(mod mi).因为mi与所有的mj(ji)互素,mi与Mi 也互素,所以Mi有模mi逆,设为Mi1.取yi=ai Mi1,则xi=Miyi=ai Mi 1Mi 满足要求.得方程组的解 x=a1M11M1+a2M21M2+akMk 1Mk,课件,15,最后,证明惟一性.设同余方程组有两个解c1和c2,则对每一个i,c1和c2模mi同余,即mi|c1c2.又m1,m2,m

9、k两两互素,故有m|c1c2,即c1和c2模m同余.,中国剩余定理的证明(续),课件,16,设正整数m1,m2,mk两两互素,一次同余方程组 xai(mod mi),i=1,2,k(1)计算m=m1m2mk(2)计算Mi=m/mi=m1mi 1mi+1mk,i=1,2,k(3)计算Mi1(mod mi),i=1,2,k(4)计算xa1M11M1+a2M21M2+akMk1Mk(mod m),一次同余方程组的求解步骤,课件,17,实例,例3 解“物不知数”问题,即求下述方程组的正整数解:x2(mod 3),x3(mod 5),x2(mod 7),解 这里m1=3,m2=5,m3=7,m=105.

10、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(mod 105).解为105k+23,k=0,1,2,.最小正整数解是23.,课件,18,大整数算术运算,设m1,m2,mk大于1且两两互素,m=m1m2mk.对任意的0 xm,令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+

11、y1)mod m1,(x2+y2)mod m2,(xk+yk)mod mk),xy=(x1y1)mod m1,(x2y2)mod m2,(xkyk)mod mk),xy=(x1y1mod m1,x2y2mod m2,xkykmod mk).,课件,19,实例,例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

12、)=(7,0,2),xy=(24mod 9,66mod 7,03mod 5)=(8,1,0).求下述方程组的最小正整数解: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),课件,20,实例(续),计算如下: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

13、(1)35+1545+0263)mod 315=260.,课件,21,大整数算术运算(续),取mi=1,记A=,设 x=atAt+at1At1+a1A+a0,其中0aj71044.这就可以用上述方法计算结果不超过71044的整数加、减、乘.,课件,22,11.5 欧拉定理和费马小定理,欧拉函数欧拉定理费马小定理,课件,23,欧拉(Eular)定理,欧拉函数(n):0,1,n1中与n互素的数的个数 例如(1)=(2)=1,(3)=(4)=2.当n为素数时(n)=n1;当n为合数时(n)n1.定理11.12(欧拉定理)设a与n互素,则 a(n)1(mod n).,课件,24,欧拉定理的证明,证 设

14、r1,r2,r(n)是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).,课件,25,费马(Fermat)小定理,定理11.13(费马小定理)设p是素数,a与p互素,则 ap-11(mod p).另一种形式是,设p是素数,则对任意的整数a,apa(mod p).费马小定理提供了一种不用因子分解就能断定一个数是合数的新途径.例如,2914(mod 9),可以断定9是合数.,