剩余类与完全剩余系ppt课件

3.2剩余类与完全剩余系,一、剩余类,按余数的不同对整数分类,是模m的一个剩余类，,即余数相同的整数构成m的一个剩余类。,一个剩余类中任意一个数称为它同类的数的剩余。,一个整数被正整数n除后，余数有n种情形：0，1，2，3，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。,1,定理1,2,二、完全剩余系,1.定义2,注：完全剩余系不唯一；,0,1,2,m1是模m的最小非负完全剩余系；,若把剩余系作为一个集合，则可以把对模m的余数相同的整数即同一剩余类里的整数，看作同一元素。,3,完全剩余系举例：,集合0,6,7,13,24是模5的一个完全剩余系，,集合0,1,2,3,4是模5的最小非负完全剩余系。,都是模m的绝对最小完全剩余系。,是模m的绝对最小完全剩余系。,4,2、完全剩余系的构造,定理2整数集合A是模m的完全剩余系的充要条件是,A中含有m个整数；,A中任何两个整数对模m不同余。,注：由定理1及定义2易得证。,思考：1、既然完全剩余系是不唯一的，不同的剩余系之间存在什么关系呢？,2、一个完全剩余系的所有元素通过线性变化后，还是完全剩余系吗？,5,检验：设x1,x2,xm是模m的一个完全剩余系，,那么，b+x1,b+x2,b+xm和ax1,ax2,axm,是模m的一个完全剩余系吗？,6,定理3设m1，a，b是整数，(a,m)=1，x1,x2,xm,是模m的一个完全剩余系，则,ax1b,ax2b,axmb也是模m的完全剩余系。,证明由定理2，只需证明：若xixj，,则axibaxjb(modm)。,假设axibaxjb(modm)，,则axiaxj(modm)，且(a,m)=1，,xixj(modm),由3.1中的结论,P50第三行知：,7,注意：,(1)在定理3中，条件(a,m)=1不可缺少，否则不能成立；,(2)定理3也可以叙述为：设m1，a，b是整数，,(a,m)=1，若x通过模m的一个完全剩余系，,则ax+b也通过模m的一个完全剩余系；,（3）特别地，若x通过模m的一个完全剩余系，(a,m)=1，则ax和x+b也分别通过模m的一个完全剩余系。,8,例2设A=x1,x2,xm是模m的一个完全剩余系，以x表示x的小数部分，证明：若(a,m)=1，则,证：当x通过模m的完全剩余系时，axb也通过模m的完全剩余系，,因此对于任意的i（1im），axib一定且只与某个整数j（1jm）同余，,即存在整数k，使得axib=kmj，（1jm）,9,3、剩余系间的联系,定理4设m1,m2N，AZ，(A,m1)=1，,分别是模m1与模m2的完全剩余系，,则R=Axm1y：xX，yY是模m1m2的一个,完全剩余系。,证明由定理3只需证明：若x,xX，y,yY，且,Axm1yAxm1y(modm1m2)，,10,例1设p5是素数，a2,3,p1，则在数列a，2a，3a，(p1)a，pa中有且仅有一个数b，满足b1(modp)；,证：因为1，2，3，(p1)，p是模p的一个完全剩余系，,所以a，2a，3a，(p1)a，pa构成模p的一个完全剩余系。,因此必有唯一的数b满足式b1(modp)。,11,AxAx(modm1),xx(modm1),x=x，,m1ym1y(modm1m2),yy(modm2),y=y。,证：Axm1yAxm1y(modm1m2)，,Axm1yAxm1y(modm1)，,由x=x，,Axm1yAxm1y(modm1m2)，,12,推论若m1,m2N，(m1,m2)=1，当x1与x2分别通过,模m1与模m2的完全剩余系时，,则m2x1m1x2通过模m1m2的完全剩余系。,13,证：由定理3只需证明，若xi,xiXi，1in，,A1x1A2x2AnxnA1x1A2x2Anxn(modm1mn),则可以得到xi=xi，1in.,事实上，由条件3假设易得，,对于任意的i，1in，有,AixiAixi(modmi)证明方法同定理4。,再利用条件2推得xixi(modmi)，,因此xi=xi.,14,15,16,17,18,19,定理5设miN，AiZ（1in），并且满足：,(mi,mj)=1，1i,jn，ij；,(Ai,mi)=1，1in；,miAj，1i,jn，ij。,则当xi（1in）通过模mi的完全剩余系Xi时，,y=A1x1A2x2Anxn通过模m1m2mn的,完全剩余系。,20,例3设m0是偶数，a1,a2,am与b1,b2,bm,都是模m的完全剩余系，,则a1b1,a2b2,ambm不是模m的完全剩余系。,证由1,2,m与a1,a2,am都是模m的完全剩余系，,如果a1b1,a2b2,ambm是模m的完全剩余系，,不可能！,21,例4设miN（1in），则当xi通过模mi（1in）,的完全剩余系时，,x=x1m1x2m1m2x3m1m2mn1xn,通过模m1m2mn的完全剩余系。,证明对n施行归纳法。,当n=2时，由定理4知定理结论成立。,假设定理结论当n=k时成立，,即当xi（2ik1）分别通过模mi的完全剩余系时，,y=x2m2x3m2m3x4m2mkxk1,通过模m2m3mk1的完全剩余系。,22,y=x2m2x3m2m3x4m2mkxk1,通过模m2m3mk1的完全剩余系。,由定理4，当x1通过模m1的完全剩余系，,xi（2ik1）通过模mi的完全剩余系时，,x1m1y=x1m1(x2m2x3m2mkxk1),=x1m1x2m1m2x3m1m2mkxk1,通过模m1m2mk1的完全剩余系。,即结论对于n=k1也成立。,23,三、与抽象代数的关系,若将模m的剩余类作为元素，则同余剩