完系、简系、剩余类(讲稿)

2014年希望联盟数学竞赛(兰州)

完系、简系、剩余类

定义1．剩余类：把关于模m同余的数归于一类，每类称为一个模m的剩余类. 即由关于模m同余的数组成的 集合，每一个集合叫做关于模m的一个剩余类(又叫同余类)．共有m个剩余类.

设Kr是余数为r的剩余类, 则Kr＝{qm＋r| m是模, r是余数, q∈Z}＝{a |a∈Z且a≡r(mod m)}.

剩余类的性质：⑴ Z＝K0∪K1∪K2∪ ∪Km 1，当i≠j时，Ki∩Kj＝Ø；

n∈Z，有唯一的r∈{0, 1, 2, , m 1}，使得n∈Kr；⑶ 对∨ a, b∈Z，a, b∈Kr a≡b (mod m) ⑵ 对于∨

定义2. 完系：设K0，K1， ，Km 1是模m的m个剩余类，从Kr中各取一数ar 作为代表，则这样的m个数 a0，a1， ，am 1称为模m的一个完全剩余系，简称m的完系. 例如：1, 2, 3, , m.

若一组数y1, y2, , ys满足：对任意整数a有且仅有一个yj，使得a≡yj (mod m)，则y1, y2, , ys是模m的 完全剩余系.

模m的完全剩余系有无穷多个，但最常用的是下面两个：① 最小非负剩余系：0, 1, 2, 3, , m 1；

② 最小绝对值剩余系：(随m的奇偶性略有区别) 当m＝2k+1时，为 k, k+1, , 1, 0, 1, 2, , k 1, k； 当m＝2k时，为 k+1, k+2, , 1, 0, 1, 2, , k 或 k, k+1, , 1, 0, 1, 2, , k 2, k 1.

例如，集合{0, 6, 7, 13, 24}是模5的一个完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系. 性质：(i) m个整数构成模m的一完全剩余系 两两对模m不同余；

(ii) 若(a, m)＝1，则x与ax＋b同时跑遍模m的完全剩余系.

完全剩余系的判断方法：

定理1：a1, a2, , am是模m的一个完全剩余系 ai／≡aj (mod m), i≠j；

定理2：设(a, m)＝1, b∈Z, 若x1, x2, , xm是模m的一个完全剩余系，则ax1＋b, ax2＋b, , axm＋b也是

模m的一个完全剩余系；特别地，m个连续的整数构成模m的一个完系.

设Kr是模的一个剩余类, 若a, b∈Kr，则a≡b(mod m), 于是(a, m)＝(b, m).

因此，若(a, m)＝1，则Kr中的任一数均与m互质, 这样，又可给出如下定义：

定义3. 简系：如果r与m互质，那么Kr中每一个数均与m互质，称Kr为与模m互质的剩余类．

这样的剩余类共有φ(m)个，从中各取一个代表(共取φ(m)个)，它们称为模m的简化剩余系，简称简系． 当m为质数p时，简系由p 1个数组成．又如：m＝6，在模6的六个剩余类中：K1＝{ , 11, 5, 1, 7, 13, } K5＝{ , 7, 1, 5, 11, 17, }是与模6互质的剩余类，数组1, 5；7, 7；1, 1；等等都是模6的简系.

性质：①Kr与模m互质 Kr中有一个数与m互质；

②与模m互质的剩余类的个数等于φ(m)；

③若(a, m)＝1, 则x与ax同时跑遍模m的简化剩余系.

简化剩余系的判断方法：

定理3：a1，a2， ，aφ(m)是模m的简化剩余系 (ai, m)＝1, 且ai≡／aj (mod m) (i≠j, i, j＝1, 2, , φ(m)). 定理4：在模m的一个完全剩余系中,取出所有与m互质的数组成的数组,就是一个模m的简化剩余系. 定理5：设(k, m)＝1, 若a1, a2, , aφ(m)是模m的简系, 则ka1, ka2, , kaφ(m)也是模m的简系.

这三个定理中，定理3与定理5是简化剩余系的判别方法，定理4是它的构造方法. 显然，模m的简化剩余系