离散数学--11.3-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,同余关系是等价关系,即同余关系具有,自反性.,a,a,(mod,m,),传递性.,a,b,(mod,m,),b,c,(mod,m,),a,c,(mod,m,).,对称性.,a,b,(mod,m,),b,a,(mod,m,).,缩写,a,1,a,2,a,k,(mod,m,).,性质11.3.2,(,模算术运算,),若,a,b,(mod,m,),c,d,(mod,m,),则,a,c,b,d,(mod,m,),ac,bd,(mod,m,),a,k,b,k,(mod,m,),其中,k,是非负整数.,性质11.3.3,设,d,1,d,|,m,则,a,b,(mod,m,),a,b,(mod,d,).,性质11.3.4,设,d,1,则,a,b,(mod,m,),da,db,(mod,dm,).,性质11.3.5,设,c,m,互素,则,a,b,(mod,m,),ca,cb,(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,3,455,的个位数是多少?,解 设3,455,的个位数为,x,则3,455,x,(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,方程,ax,c,(mod,m,),有解的充要条件是,gcd,(,a,m,)|,c,.,证 充分性.记,d,=gcd,(,a,m,),a,=,da,1,m,=,dm,1,c,=,dc,1,其中,a,1,与,m,1,互素.由定理11.,8,存在,x,1,和,y,1,使得,a,1,x,1,+,m,1,y,1,=1.,令,x,=,c,1,x,1,y,=,c,1,y,1,得,a,1,x,+,m,1,y,=,c,1,.,等式两边同乘,d,得,ax,+,my,=,c,.,所以,ax,c,(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)设,ab,1,1(mod,m,),ab,2,1(mod,m,).,得,a,(,b,1,b,2,)0(mod,m,).,由,a,与,m,互素,b,1,b,2,0(mod,m,),得证,b,1,b,2,(mod,m,).,定义11.6,如果,ab,1(mod,m,),则称,b,是,a,的,模,m,逆,记作,a,1,(mod,m,),或,a,1,.,a,1,(mod,m,),是方程,ax,1(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,使得 5,b,+7,k,=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.1,1(,中国剩余定理),设正整数,m,1,m,2,m,k,两两互素,则一次同余方程组,x,a,i,(mod,m,i,),i,=1,2,k,有整数解,并且在模,m,=,m,1,m,2,m,k,下解是惟一的,即任意两,个解都是模,m,同余的,.,孙子算经,“物不知数”问题,:,今有物,不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何,?,x,2(mod 3),x,3(mod 5),x,2(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,最后,证明惟一性,.,设同余方程组有两个解,c,1,和,c,2,则,对每一,个,i,c,1,和,c,2,模,m,i,同余,即,m,i,|,c,1,c,2,.,又,m,1,m,2,m,k,两两互素,故有,m,|,c,1,c,2,即,c,1,和,c,2,模,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,解“物不知数”问题,即求下述方程组的正整数解:,x,2(mod 3),x,3(mod 5),x,2(mod 7),解 这里,m,1,=3,m,2,=5,m,3,=7,m,=105.,M,1,=57=35,M,1,2(mod 3),M,1,1,=2.,M,2,=37=21,M,2,1(mod 5),M,2,1,=1.,M,3,=35=15,M,3,1(mod 7),M,3,1,=1.,x,2235+3121+211523323(mod 105).,解为,105,k,+23,k,=0,1,2,.,最小正整数解是,23.,17,大整数算术运算,设,m,1,m,2,m,k,大于,1且,两两互素,m,=,m,1,m,2,m,k,.,对任意的,0,x,m,令,x,i,=,x,mod,m,i,i,=1,k,.,把,(,x,1,x,2,x,k,),叫作,x,关于,模,m,1,m,k,的,模表示,简称,x,的,模表示,记作,x,=(,x,1,x,2,x,k,).,模表示运算,设,x,=(,x,1,x,2,x,k,),y,=(,y,1,y,2,y,k,),则有,x,+,y,=(,x,1,+,y,1,)mod,m,1,(,x,2,+,y,2,)mod,m,2,(,x,k,+,y,k,)mod,m,k,),x,y,=(,x,1,y,1,)mod,m,1,(,x,2,y,2,)mod,m,2,(,x,k,y,k,)mod,m,k,),xy,=(,x,1,y,1,mod,m,1,x,2,y,2,mod,m,2,x,k,y,k,mod,m,k,).,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,.,这就可,以用上述方法计算结果不超过,