资源描述
1,11.3同余,同余模算术运算模m等价类,2,同余,定义11.5设m是正整数,a和b是整数.如果m|ab,则称a模m同余于b,或a与b模m同余,记作ab(modm).如果a与b模m不同余,则记作ab(modm).例如,153(mod4),160(mod4),142(mod4),1516(mod4).下述两条都是a与b模m同余的充分必要条件:(1)amodm=bmodm.(2)a=b+km,其中k是整数.,3,同余(续),性质11.3.1同余关系是等价关系,即同余关系具有自反性.aa(modm)传递性.ab(modm)bc(modm)ac(modm).对称性.ab(modm)ba(modm).缩写a1a2ak(modm).性质11.3.2(模算术运算)若ab(modm),cd(modm),则acbd(modm),acbd(modm),akbk(modm),其中k是非负整数.性质11.3.3设d1,d|m,则ab(modm)ab(modd).性质11.3.4设d1,则ab(modm)dadb(moddm).性质11.3.5设c,m互素,则ab(modm)cacb(modm).,4,模m等价类,模m等价类:在模m同余关系下的等价类.am,简记作a.Zm:Z在模m同余关系下的商集在Zm上定义加法和乘法如下:a,b,a+b=a+b,ab=ab.,例1写出Z4的全部元素以及Z4上的加法表和乘法表.,解Z4=0,1,2,3,其中i=4k+i|kZ,i=0,1,2,3.,0123123023013012,0000012302020321,5,实例,例23455的个位数是多少?,解设3455的个位数为x,则3455x(mod10).,由341(mod10),有3455=34113+3337(mod10),故3455的个位数是7.,6,实例,例3(续)例如,中华人民共和国成立日1949年10月1日,C=19,X=49,M=8,d=1,是星期六.中国人民抗日战争胜利日1945年8月15日,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(modm)有解的充要条件是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(modm).必要性.设x是方程的解,则存在y使得ax+my=c.由性质11.1.1,有d|c.,一次同余方程:axc(modm),其中m0.一次同余方程的解:使方程成立的整数例如,2x0(mod4)的解为x0(mod2),2x1(mod4)无解,9,实例,例1解一次同余方程6x3(mod9).解gcd(6,9)=3|3,方程有解.取模9等价类的代表x=4,3,2,1,0,1,2,3,4,检查它们是否是方程的解,计算结果如下:6(4)6(1)623(mod9),6(3)60630(mod9),6(2)61646(mod9),得方程的解x=4,1,2(mod9),方程的最小正整数解是2.,10,模m逆,定理11.10(1)a的模m逆存在的充要条件是a与m互素.(2)设a与m互素,则在模m下a的模m逆是惟一的.证(1)这是定理11.9的直接推论.(2)设ab11(modm),ab21(modm).得a(b1b2)0(modm).由a与m互素,b1b20(modm),得证b1b2(modm).,定义11.6如果ab1(modm),则称b是a的模m逆,记作a1(modm)或a1.a1(modm)是方程ax1(modm)的解.,11,实例,例2求5的模7逆.,解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,得513(mod7).,12,实例,例2(续),方法3.直接观察,53=15,151(mod7),得513(mod7).,13,中国剩余定理(孙子定理),定理11.11(中国剩余定理)设正整数m1,m2,mk两两互素,则一次同余方程组xai(modmi),i=1,2,k有整数解,并且在模m=m1m2mk下解是惟一的,即任意两个解都是模m同余的.,孙子算经“物不知数”问题:今有物,不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?x2(mod3)x3(mod5)x2(mod7),14,中国剩余定理的证明,假设则x=x1+x2+xk是所求的解.令Mi=m/mi,i=1,2,k.设xi=Miyi,应该有Miyiai(modmi).因为mi与所有的mj(ji)互素,mi与Mi也互素,所以Mi有模mi逆,设为Mi1.取yi=aiMi1,则xi=Miyi=aiMi1Mi满足要求.得方程组的解x=a1M11M1+a2M21M2+akMk1Mk,15,最后,证明惟一性.设同余方程组有两个解c1和c2,则对每一个i,c1和c2模mi同余,即mi|c1c2.又m1,m2,mk两两互素,故有m|c1c2,即c1和c2模m同余.,中国剩余定理的证明(续),16,设正整数m1,m2,mk两两互素,一次同余方程组xai(modmi),i=1,2,k(1)计算m=m1m2mk(2)计算Mi=m/mi=m1mi1mi+1mk,i=1,2,k(3)计算Mi1(modmi),i=1,2,k(4)计算xa1M11M1+a2M21M2+akMk1Mk(modm),一次同余方程组的求解步骤,17,实例,例3解“物不知数”问题,即求下述方程组的正整数解:x2(mod3),x3(mod5),x2(mod7),解这里m1=3,m2=5,m3=7,m=105.M1=57=35,M12(mod3),M11=2.M2=37=21,M21(mod5),M21=1.M3=35=15,M31(mod7),M31=1.x2235+3121+211523323(mod105).解为105k+23,k=0,1,2,.最小正整数解是23.,18,大整数算术运算,设m1,m2,mk大于1且两两互素,m=m1m2mk.对任意的0xm,令xi=xmodmi,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)modm1,(x2+y2)modm2,(xk+yk)modmk),xy=(x1y1)modm1,(x2y2)modm2,(xkyk)modmk),xy=(x1y1modm1,x2y2modm2,xkykmodmk).,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)mod9,(6+6)mod7,(0+3)mod5)=(6,5,3),xy=(24)mod9,(66)mod7,(03)mod5)=(7,0,2),xy=(24mod9,66mod7,03mod5)=(8,1,0).求下述方程组的最小正整数解:z6(mod9)z7(mod9)z8(mod9)z5(mod7)z0(mod7)z1(mod7)z3(mod5)z2(mod5)z0(mod5),20,实例(续),计算如下:M1=35,M11(mod9),M11=1,M2=45,M23(mod7),M21=5,M3=63,M33(mod5),M31=2,得x+y=(6(1)35+5545+3263)mod315=33.xy=(7(1)35+0545+2263)mod315=7,xy=(8(1)35+1545+0263)mod315=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(modn).,24,欧拉定理的证明,证设r1,r2,r(n)是0,1,n1中与n互素的(n)个数.由于a与n互素,对每一个1i(n),ari也与n互素,故存在1(i)(n)使得arir(i)(modn).是1,2,(n)上的映射.要证是一个单射.a的模n逆a1存在,a1也与n互素.假设ij,(i)=(j),则有ariarj(modn).两边同乘a1,得rirj(modn),矛盾.得证是1,2,(n)上的单射,当然也是1,2,(n)上的双射.从而,有而与n互素,故a(n)1(modn).,25,费马(Fermat)小定理,定理11.13(费马小定理)设p是素数,a与p互素,则ap-11(modp).另一种形式是,设p是素数,则对任意的整数a,apa(modp).费马小定理提供了一种不用因子分解就能断定一个数是合数的新途径.例如,2914(mod9),可以断定9是合数.,
展开阅读全文