高二暑假南理工夏令营
完系、简系、剩余类
定义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的简化剩余系
第 1 页 共 4页
高二暑假南理工夏令营
有无穷多个，但常用的是“最小简化剩余系”，即由1，2，?，m－1中与m互质的那些数组成的数组. 说明：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的(模)m，然后在模m的每个剩余类中取一个“代表数”(即组成一个完全剩余系)，当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.
例1、设n为偶数，a1, a2,?, an与b1, b2,?, bn均为模n的完全剩余系，试证：a1＋b1, a2＋b2,?, an＋bn不是模的完全剩余系. 证明：假设a1＋b1, a2＋b2,?, an＋bn是模的完全剩余系. ∴?(ai?bi)?1+2+i?1nnn+n?n(n?1)n?(modn) 22nn(n?1)nn?(modn)，同理有：?bi?(modn) ∵a1, a2,?, an也是模的完全剩余系. ∴?ai??i?i?1i?1i?1222??(ai?bi)?n?0(modn)，∴n|2, 矛盾！故假设不成立，从而原命题成立.
i?1nn
例2、设m＞1, (a, m)＝1，b∈Z, 求和：?{i?0m?1a?i?b}, 其中{x}为x的小数部分. m解：∵i取遍模m的完系，令xi＝a·i＋b，则也取遍模m的完系.
m?1km?1ka?i?bm?1xi11m?1}??{}??{}????m(m?1)? 故?{
i?0i?0mk?0mk?0mmm22m?1总结：若a1, a2,?, am是模m的一个完系，则①a1＋a2＋?＋am≡1＋2＋?＋m (mod m)； ②a1·a2·??·am≡1·2·?·m (mod m)； ③(a1)n＋(a2)n＋?＋(am)n≡1n＋2n＋?＋mn (mod m). 例3、已知m, n为正整数, 且m为奇数, (m, 2n－1)＝1. 证明：m|
?kk?1mn.
证明：∵1, 2, ?, m构成模m的完系, (m, 2)＝1，∴2, 4, ?, 2m也构成模m的完系. ∴
?(2k)k?1mn??k(modm)，即(2?1)?k?0(modm). ∵(m, 2－1)＝1，∴m|?kn得证.
nnnn
mmmk?1k?1k?1例4、求八个整数n1, n2,?, n8满足：对每个整数k (－2014＜k＜2014)，有八个整数a1, a2,?, an∈{?1, 0, 1}, 使得k＝a1n1＋a2n2＋?＋a8n8 解：令G＝{k| k＝a1＋a2·2＋a3·32＋?＋an+1·3n，ai∈{?1, 0, 1}，i＝1，2，?，n＋1}.
3n+1－12n
显然maxG＝1＋3＋3＋?＋3＝(记为H)，minG＝－1－3－32＋?－3n＝－H.
2
n+1
且G中的元素个数有3＝2H＋1个， 又∵G中任意两数之差的绝对值不超过2H， ∴G中的数对模2H＋1不同余，∴G的元素恰好是模2H＋1的一个绝对值最小的完系， 于是凡满足－H?k?H的任意整数都属于G，且可唯一地表示为a1＋a2·2＋a3·32＋?＋an+1·3n形式， 当n＝7时，H＝3208＞2014，而n＝6时，H＝1043＜2014，故n1＝1，n2＝3，?，n8＝37为所求.
1111a
例5、已知p为大于3的质数，且2＋2＋2＋?＋2＝，a，b∈N*. (a, b)＝1，证明：pa. 123(p－1)b证明：对于不超过p?1的自然数k，由于(k, p)＝1，所以存在唯一的不超过p?1的自然数x，满足kx?1(modp)而且，当k＝1或p?1有x＝1或p?1，当2?k?p?2时，有2?x?p?2,x?k，
故当k取遍1，2，??，p?1时，x也取遍1，2，??，p?1，因为(p,(p?1)!)?1,由kx?1(modp)可得到
第 2 页 共 4页
高二暑假南理工夏令营
(p?1)!kx?(p?1)!(modp)或(p?1)!x?(p?1)!(modp),所以 k((p?1)!)2ap?1((p?1)!)2p?1222p(p?1)(2p?1)???((p?1)!)x?((p?1)!)(modp) ?2bk6k?1x?1因为p是大于3的素数，所以p?1不小于4，所以(p?1)!含有因数6，
p(p?1)(2p?1)((p?1)!)2a?0(modp)，即?0(modp)， 从而((p?1)!)6b2因为(p,(p?1)!)?1，所以(p,((p?1)!)2)?1，从而
a?0(modp)?a?0(modp) bn
例6、(2003克罗地亚奥林匹克) 对于所有奇质数p和正整数n (n?p)，试证：Cnp≡[] (mod p)
p
例7、(第26届IMO) 设n为正整数，整数k与n互质，且0＜k＜n. 令M＝{1, 2, ?, n?1}(n?3), 给M中每个数染上黑白两种染色中的一种，染法如下：⑴对M中的每个i，i与n?i同色，⑵对M中每个i，i≠k，i与|k?i|同色，试证：M中所有的数必为同色. 证明：∵(k, n)＝1且0，1，2，?，n?1是一个模n的最小非负完系， ∴0·k，1·k，2·k，?，(n?1)·k也是一个模n的完全剩余系.
若设rj≡j·k(mod n)(其中1?rj?n－1，j＝1，2，?，n－1) ，则M＝{1，2，?，n?1}＝{r1,r2,?,rn?1} 下面只要证明rj与rj+1(j＝1，2，?，n?2)同色即可. 因为若如此，当r1颜色确定后，M中所有的数都r1与同色. 由于(j＋1)k≡rj+1(mod n)，则rj＋k≡rj+1(mod n)，因此
若rj＋k＜n，则rj+1＝rj+k，由条件⑵知rj+1与| rj+1－k|＝rj同色；
若rj＋k＞n，由rj+1＝rj+k－n，由条件⑴知k－rj+1＝n—rj与n－(n—rj)＝rj同色，即k－rj+1与rj同色， 由条件⑵知k－rj+1与|k－(k－rj+1)|＝rj+1同色，因此rj+1与rj同色.
综上：此rj+1与rj同色. 故M中所有的数必为同色.
例8、(2001第42届IMO)设n为奇数且大于1，k1, k2,?, kn为给定的整数，对于1, 2, ?, n的n!个排列中的每一
第 3 页 共 4页
高二暑假南理工夏令营
个排列a＝(a1, a2,?, an)，记S(a)＝
?kaii?1ni，试证：有两个排列b和c，使得n!| S(b)－S(c).
证明：假设对任意两个不同的b和c，均有S(b)／≡S(c)(mod n!)，则当a取遍所有1，2，?，n的n!个排列时， S(a)也取遍模n!的一个完全剩余系，且每个剩余系恰好经过一次，所以
1n!n!n!
?S(a)≡1+2+3+?+n!(mod n!)≡2(n!+1)n!≡2×n!＋2≡2(mod n!) (n＞1) a其中?S(a)表示对取遍个排列求和(下同)，下面用另一种方法计算?S(a)??(?kiai)：
aaai?1n对于k1，i∈{1，2，?，n}，ai＝1时，剩n－1个数，有(n－1)!个排列，ai＝2时，有(n－1)!个排列，?
(n?1)!n1
∴k1的系数为(n－1)!·(1+2+?+n)＝(n+1)!. ∴?S(a)＝?ki 2i?1a2(n?1)!nn!但?S(a)＝?ki≡0(mod n!) (∵n为奇数)，∴2≡0(mod n!), 矛盾. ∴n!| S(b)－S(c).
i?1a2
例9、设m是给定的整数. 求证：存在整数a，b和k. 其中a，b均为奇数，k?0，使得2m＝a19＋b99＋k·21999.
另解：设x，y为奇数，若x／≡y(mod 21999)，则x19－y19＝(x－y)(x18＋x17y＋?＋xy17＋y18)， ∵x18＋x17y＋?＋xy17＋y18为奇数，∴x18＋x17y＋?＋xy17＋y18与21999互质，∴x19／≡y19(mod 21999) 故当a取遍模21999的简化剩余系时，a19也取遍模21999的简化剩余系，
∴一定存在a，使得a19≡2m－1(mod 21999)，并且有无穷多个这样的a，故2m－1－a19＝k·21999 令b＝1，则2m＝a19＋b99＋k·21999. 当a足够小时，不难知k?0.
第 4 页 共 4页