剩余类与完全剩余系

《剩余类与完全剩余系》由会员分享，可在线阅读，更多相关《剩余类与完全剩余系（24页珍藏版）》请在金锄头文库上搜索。

1、3.2 3.2 剩余类与完全剩余系剩余类与完全剩余系 一、剩余类一、剩余类 按余数的不同对整数分类按余数的不同对整数分类 是模是模m的一个剩余的一个剩余类， 即即 余数相同的整数构成余数相同的整数构成m的的一个剩余一个剩余类。一个剩余一个剩余类中任意一个数称中任意一个数称为它同它同类的数的剩余。的数的剩余。一个整数被正整数一个整数被正整数n除后，余数有除后，余数有n种情形：种情形：0 0，1 1，2 2，3 3，n-1-1，它们彼此对模，它们彼此对模n不同余。这表明，每个不同余。这表明，每个整数恰与这整数恰与这n个整数中某一个对模个整数中某一个对模n同余。这样一来，同余。这样一来，按模按模n是

2、否同余对整数集进行分类，可以将整数集分是否同余对整数集进行分类，可以将整数集分成成n个两两不相交的子集。个两两不相交的子集。定理定理1 1 二、完全剩余系二、完全剩余系1.1.定义定义2 2 注：注： 完全剩余系不唯一；完全剩余系不唯一； 0, 1, 2, , m 1是模是模m的最小非的最小非负完全剩余系；完全剩余系； 若把剩余系作若把剩余系作为一个集合，一个集合，则可以把可以把对模模m的余的余数相同的整数数相同的整数即同一剩余即同一剩余类里的整数，看作同里的整数，看作同一元素。一元素。完全剩余系举例：完全剩余系举例：集合集合0, 6, 7, 13, 24是模是模5的一个完全剩余系，的一个完全

3、剩余系，集合集合0, 1, 2, 3, 4是模是模5的最小非的最小非负完全剩余系。完全剩余系。都是模都是模m的的绝对最小完全剩余系。最小完全剩余系。是模是模m的的绝对最小完全剩余系。最小完全剩余系。 2 2、完全剩余系的构造、完全剩余系的构造定理定理2 2 整数集合整数集合A是模是模m的完全剩余系的充要条件是的完全剩余系的充要条件是 A中含有中含有m个整数；个整数； A中任何两个整数中任何两个整数对模模m不同余。不同余。注：由定理注：由定理1 1及定义及定义2 2易得证。易得证。思考思考：1 1、既然完全剩余系是不唯一的，不同的剩余系、既然完全剩余系是不唯一的，不同的剩余系 之间存在什么关系呢

4、？之间存在什么关系呢？2 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的完全剩余系。的完全剩余系。证明明 由定理由定理

5、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.13.1中的结论中的结论,P50,P50第三行知：第三行知： 注意：注意：(1)(1)在定理在定理3 3中，条件中，条件(a, m) = 1不可缺少，否不可缺少，否则不能不能 成立；成立；(2) 定理定理3也可以叙述也可以叙述为：设m 1，a，b是整数，是整数，(a, m) = 1，若若x通通过模模m的一个完全剩余系，的一个完全剩余系，则ax+b也通也通过模模m

6、的一个完全剩余系；的一个完全剩余系；（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）同余

7、，）同余， 即存在整数即存在整数k，使得，使得 axi b = km j，（，（1 j m）3 3、剩余系间的联系、剩余系间的联系定理定理4 设m1, m2 N，A Z，(A, m1) = 1，分分别是模是模m1与模与模m2的完全剩余系，的完全剩余系， 则 R = Ax m1y：x X，y Y 是模是模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中有且中有

8、且仅有有一个数一个数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)。定理定理4 设m1, m2 N，A Z，(A, m1) = 1，分分别是模是模m1与模与模m2的完全剩余系，的完全剩余系， 则 R = Ax m1y：x X，y Y 是模是模m1m2的一个的一个Ax Ax (mod m1) x x (mod m1) x = x ， m1y m1y (mod m

9、1m2) 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, m2 N，(m1, m2) = 1，当当x1与与x2分分别通通过 模模m1与模与模m2的完全剩余系的完全剩余系时， 则 m2x1 m1x2通通过模模m1m2的完全剩余系。的完全剩余系。 证： 由定理由定理3只需只需证明，若明，若xi , xiXi，1 i n， A1x1 A2x2 Anxn A1x1 A2x2 Anxn (mod m1mn) 则 可以得

10、到可以得到 xi = xi ，1 i n.事事实上，由条件上，由条件3假假设易得，易得， 对于任意的于任意的i，1 i n，有，有Aixi Aixi (mod mi)证明方法同定理明方法同定理4。再利用条件再利用条件2推得推得 xi xi (mod mi)，因此因此xi = xi . 定理定理5 设mi N，Ai Z（1 i n），并且），并且满足：足： (mi, mj) = 1，1 i, j n，i j； (Ai, mi) = 1，1 i n； mi Aj ，1 i, j n，i j 。则当当xi（1 i n）通）通过模模mi的完全剩余系的完全剩余系Xi时，y = A1x1 A2x2 Anx

11、n 通通过模模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 设mi N（1 i n），），则当当xi通通过模模mi（1 i n） 的完全剩余系时，的完全剩余系时，x = x1 m

12、1x2 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的完全剩余系，的完全剩余系

13、， 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为质数数时，上述的，上述的环又可以构成一个有限域。又可以构成一个有限域。