离散数学--113-5同余

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,11.3,同余,同余,模算术运算,模,m,等价类,1,同余,定义11.5,设,m,是正整数,a,和,b,是整数.如果,m,|,a,b,则称,a,模,m,同余于,b,或,a,与,b,模,m,同余,记作,a,b,(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,是整数.,2,同余(续),性质11.3.1 同余关系是等价关系,即同余关系具有,自反性.aa(mod m),传递性.ab(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,等价类,:在模,m,同余关系下的等价类.,a,m,简记作,a,.,Z,m,:,Z,在模,m,同余关系下的商集,在,Z,m,上定义加法和乘法如下:,a,b,a,+,b,=,a,+,b,a,b,=,ab,.,+,0 1 2 3,0,1,2,3,0 1 2 3,0,1,2,3,例1,写出,Z,4,的全部元素以及,Z,4,上的加法表和乘法表.,解,Z,4,=0,1,2,3,其中,i,=4,k,+,i,|,k,Z,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,4,实例,例2 3455的个位数是多少,解 设3455的个位数为x,那么3455x(mod10).,由3,4,1(,mod 10),有 3,455,=3,4,113+3,3,3,7(,mod 10),故3,455,的个位数是7.,例3,日期的星期数,y,年,m,月,d,日星期数的计算公式:,其中,M,=(,m,3)mod12+1,Y,=,y,M,/11,=100,C,+,X,Y,年,M,月:3月下一年2月,C,:,Y,年的世纪数,),7,(mod,12,/,2,/,),7,/,(,2,2,4,/,4,/,d,m,M,M,M,C,C,X,X,w,+,+,+,+,+,-,+,+,5,实例,例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.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.由性质,11.1.1,有d|c.,一次同余方程,:,ax,c,(mod,m,),其中,m,0.,一次同余方程的,解,:使方程成立的整数,例如,2,x,0(mod 4),的解为,x,0(mod 2),2,x,1(mod 4),无解,8,实例,例1,解一次同余方程 6,x,3(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.,9,模,m,逆,定理11.10 (1)a的模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)的解.,10,实例,例2,求5的模7逆.,解 5与7互素,故5的模7逆存在.,方法1,.解方程5,x,1(mod7).,检查,x,=,3,2,1,0,1,2,3,得到 5,1,3(,mod7).,方法2.做辗转相除法,求得整数b,k使得 5b+7k=1,那么b是,5的模7逆.,计算如下:,7=5+2,5=22+1.,回代 1=5,22=5,2(7,5)=35,27,得 5,1,3(,mod7).,11,实例,例2,(,续,),方法,3,.,直接观察,5,3=15,15,1(mod 7),得 5,1,3(,mod7).,12,中国剩余定理(孙子定理),定理11.11(中国剩余定理)设正整数m1,m2,mk两两互素,那么一次同余方程组,xai(mod mi),i=1,2,k,有整数解,并且在模m=m1m2mk下解是惟一的,即任意两,个解都是模m同余的.,孙子算经“物不知数问题:今有物,不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何,x2(mod 3),x3(mod 5),x2(mod 7),13,中国剩余定理的证明,假设,则,x,=,x,1,+,x,2,+,x,k,是所求的解,.,令,M,i,=,m/m,i,i,=1,2,k,.,设,x,i,=,M,i,y,i,应该有,M,i,y,i,a,i,(mod,m,i,).,因为,m,i,与所有的,m,j,(,j,i,),互素,m,i,与,M,i,也互素,所以,M,i,有模,m,i,逆,设为,M,i,1,.,取,y,i,=,a,i,M,i,1,则,x,i,=,M,i,y,i,=,a,i,M,i,1,M,i,满足要求.,得方程组的解,x,=,a,1,M,1,1,M,1,+,a,2,M,2,1,M,2,+,a,k,M,k,1,M,k,14,最后,证明惟一性.设同余方程组有两个解c1和c2,那么对每一,个i,c1和c2模mi同余,即mi|c1c2.又m1,m2,mk两两互素,故有m|c1c2,即c1和c2模m同余.,中国剩余定理的证明(续),15,设正整数,m,1,m,2,m,k,两两互素,一次同余方程组,x,a,i,(mod,m,i,),i,=1,2,k,(1)计算,m,=,m,1,m,2,m,k,(2)计算,M,i,=,m/m,i,=,m,1,m,i,1,m,i,+1,m,k,i,=1,2,k,(3)计算,M,i,1,(,mod,m,i,),i,=1,2,k,(4)计算,x,a,1,M,1,1,M,1,+,a,2,M,2,1,M,2,+,a,k,M,k,1,M,k,(mod,m,),一次同余方程组的求解步骤,16,实例,例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(mod 105).,解为105k+23,k=0,1,2,.最小正整数解是23.,17,大整数算术运算,设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+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).,18,实例,例4,取,m,1,=9,m,2,=7,m,3,=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),x,y,=(2,4)mod 9,(6,6)mod 7,(0,3)mod 5)=(7,0,2),xy,=(24mod 9,66mod 7,03mod 5)=(8,1,0).,求下述方程组的最小正整数解:,z,6(mod 9),z,7(mod 9),z,8(mod 9),z,5(mod 7),z,0(mod 7),z,1(mod 7),z,3(mod 5),z,2(mod 5),z,0(mod 5),19,实例(续),计算如下:,M,1,=35,M,1,1(mod 9),M,1,1,=,1,M,2,=45,M,2,3(mod 7),M,2,1,=5,M,3,=63,M,3,3(mod 5),M,3,1,=2,得,x,+,y,=(6(,1)35+5545+3263)mod 315=33.,x,y,=(7(,1)35+0545+2263)mod 315=7,xy,=(8,(,1),35+1,5,45+0,2,63)mod 315=260.,20,大整数算术运算(续),取,m,i,=,1,记,A,=,设,x,=,a,t,A,t,+,a,t,1,A,t,1,+,a,1,A,+,a,0,其中0,a,j,7,10,44,.,这就可,以用上述方法计算结果不超过,7,10,44,的整数加、减、乘,.,21,11.5,欧拉定理和费马小定理,欧拉函数,欧拉定理,费马小定理,22,欧拉(,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).,23,欧拉定理的证明,证 设,r,1,r,2,r,(,n,),是0,1,n,1,中与,n,互素的,(,n,),个数.,由于,a,与,n,互素,对每一个1,i,(,n,),ar,i,也与,n,互素,故存,在1,(,i,),(,n,),使得,ar,i,r,(,i,),(mod,n,).,是1,2,(,n,),上的映射.要证,是一个单射,.,a,的模,n,逆,a,1,存在,a,1,也与,n,互素.,假设,i,j,(,i,)=,(,j,),则有,ar,i,ar,j,(mod,n,).,两边同乘,a,1,得,r,i,r,j,(mod,n,),矛盾.得证,是1,2,(,n,),上的单射,当然也是1,2,(,n,),上的,双射.从而,有,而 与,n,互素,故,a,(,n,),1(m