剩余类与完全剩余系.ppt
3.2 剩余类与完全剩余系,一、剩余类,按余数的不同对整数分类,是模m的一个剩余类，,即 余数相同的整数构成m的一个剩余类。,一个剩余类中任意一个数称为它同类的数的剩余。,一个整数被正整数n除后，余数有n种情形：0，1，2，3，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。,定理1,二、完全剩余系,1.定义2,注：完全剩余系不唯一；,0,1,2,m 1是模m的最小非负完全剩余系；,若把剩余系作为一个集合，则可以把对模m的余数相同的整数即同一剩余类里的整数，看作同一元素。,完全剩余系举例：,集合0,6,7,13,24是模5的一个完全剩余系，,集合0,1,2,3,4是模5的最小非负完全剩余系。,都是模m的绝对最小完全剩余系。,是模m的绝对最小完全剩余系。,2、完全剩余系的构造,定理2 整数集合A是模m的完全剩余系的充要条件是,A中含有m个整数；,A中任何两个整数对模m不同余。,注：由定理1及定义2易得证。,思考：1、既然完全剩余系是不唯一的，不同的剩余系 之间存在什么关系呢？,2、一个完全剩余系的所有元素通过线性变化后，还是完全剩余系吗？,检验：设x1,x2,xm是模m的一个完全剩余系，,那么，b+x1,b+x2,b+xm和 ax1,ax2,a xm,是模m的一个完全剩余系吗？,定理3 设m 1，a，b是整数，(a,m)=1，x1,x2,xm,是模m的一个完全剩余系，则,ax1 b,ax2 b,axm b也是模m的完全剩余系。,证明 由定理2，只需证明：若xi xj，,则 axi b axj b(mod m)。,假设 axi b axj b(mod m)，,则 axi axj(mod m)，且(a,m)=1，,xi xj(mod m),由3.1中的结论,P50第三行知：,注意：,(1)在定理3中，条件(a,m)=1不可缺少，否则不能 成立；,(2)定理3也可以叙述为：设m 1，a，b是整数，,(a,m)=1，若x通过模m的一个完全剩余系，,则ax+b也通过模m的一个完全剩余系；,（3）特别地，若x通过模m的一个完全剩余系，(a,m)=1，则ax和x+b也分别通过模m的一 个完全剩余系。,例2 设A=x1,x2,xm是模m的一个完全剩余系，以x表示x的小数部分，证明：若(a,m)=1，则,证：当x通过模m的完全剩余系时，ax b也通过模m的完全剩余系，,因此对于任意的i（1 i m），axi b一定且只与某个整数j（1 j m）同余，,即存在整数k，使得 axi b=km j，（1 j m）,3、剩余系间的联系,定理4 设m1,m2N，AZ，(A,m1)=1，,分别是模m1与模m2的完全剩余系，,则 R=Ax m1y：xX，yY 是模m1m2的一个,完全剩余系。,证明 由定理3只需证明：若x,x X，y,y Y，且,Ax m1y Ax m1y(mod m1m2)，,例1 设p 5是素数，a 2,3,p 1，则在数列a，2a，3a，(p 1)a，pa中有且仅有一个数b，满足 b 1(mod p)；,证：因为1，2，3，(p 1)，p是模p的 一个完全剩余系，,所以a，2a，3a，(p 1)a，pa构成模p的 一个完全剩余系。,因此必有唯一的数b满足式b 1(mod p)。,Ax Ax(mod m1),x x(mod m1),x=x，,m1y m1y(mod m1m2),y y(mod m2),y=y。,证：Ax m1y Ax m1y(mod m1m2)，,Ax m1y Ax m1y(mod m1)，,由x=x，,Ax m1y Ax m1y(mod m1m2)，,推论 若m1,m2N，(m1,m2)=1，当x1与x2分别通过,模m1与模m2的完全剩余系时，,则 m2x1 m1x2通过模m1m2的完全剩余系。,证：由定理3只需证明，若xi,xiXi，1 i n，,A1x1 A2x2 Anxn A1x1 A2x2 Anxn(mod m1mn),则 可以得到 xi=xi，1 i n.,事实上，由条件3假设易得，,对于任意的i，1 i n，有,Aixi Aixi(mod mi)证明方法同定理4。,再利用条件2推得 xi xi(mod mi)，,因此xi=xi.,定理5 设miN，AiZ（1 i n），并且满足：,(mi,mj)=1，1 i,j n，i j；,(Ai,mi)=1，1 i n；,miAj，1 i,j n，i j。,则当xi（1 i n）通过模mi的完全剩余系Xi时，,y=A1x1 A2x2 Anxn 通过模m1m2mn的,完全剩余系。,例3 设m 0是偶数，a1,a2,am与b1,b2,bm,都是模m的完全剩余系，,则a1 b1,a2 b2,am bm不是模m的完全剩余系。,证 由1,2,m与a1,a2,am都是模m的完全剩余系，,如果a1 b1,a2 b2,am bm是模m的完全剩余系，,不可能！,例4 设miN（1 i n），则当xi通过模mi（1 i n）,的完全剩余系时，,x=x1 m1x2 m1m2x3 m1m2mn 1xn,通过模m1m2mn的完全剩余系。,证明 对n施行归纳法。,当n=2时，由定理4知定理结论成立。,假设定理结论当n=k时成立，,即当xi（2 i k 1）分别通过模mi的完全剩余系时，,y=x2 m2x3 m2m3x4 m2mkxk 1,通过模m2m3mk 1的完全剩余系。,y=x2 m2x3 m2m3x4 m2mkxk 1,通过模m2m3mk 1的完全剩余系。,由定理4，当x1通过模m1的完全剩余系，,xi（2 i k 1）通过模mi的完全剩余系时，,x1 m1y=x1 m1(x2 m2x3 m2mkxk 1),=x1 m1x2 m1m2x3 m1m2mkxk 1,通过模m1m2mk 1的完全剩余系。,即结论对于n=k 1也成立。,三、与抽象代数的关系,若将模m的剩余类作为元素，则 同余剩余类的相等，,同余的运算元素剩余类的运算，,剩余类的集合即是环。,特别地，当m为合数时，就有：,非零的剩余类的乘积可能为零的剩余类，,即存在零因子的环。,上述环中所有与模m互质的剩余类对乘法构成群；,当m为质数时，上述的环又可以构成一个有限域。,
