剩余类与完全剩余系

1、.,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的余 数相同的整数即同一剩余

2、类里的整数，看作同 一元素。,.,完全剩余系举例：,集合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的一个完全剩余系，,那么，

3、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不

4、可缺少，否则不能 成立；,(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

5、 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构成

6、模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只需

7、证明，若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）通过模m

8、i的完全剩余系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的完全剩余系。,

9、证明 对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也成立。,.,三、与抽象代数的关