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的一个完全剩余系 ， ,那么 ， b+x1, b+x2,。

3、, 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 axj (mod m) ，且(a, m) = 1 ， ,xi xj (mod m),由3.1中的结论,P50第三行知：,注意：,(1)在定理3中 ， 条件(a, m) = 1不可缺少 ， 否则不能 成立；,(2) 定理3也可以叙述为：设m 1 ， a ， b是整数 ，。

4、,(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 ，。

5、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 ( 。

6、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 ( 。

7、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, 。

8、 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）分别通过 。

来源：(未知)

【学习资料】网址：/a/2021/0329/0021807261.html

标题：剩余|剩余类与完全剩余系