§2.2剩余类与剩余系 由上一节性质1知,对于给定的整数模m,整数的同余关系 是所有整数构成的集合Z上的一个等价关系,因此可以由这 个等价关系诱导一个划分,即把集合Z分成m个两两互不相 交的集合,且同一个集合中的任意两个整数对模m一定同 余,而属于不同集合中的两个整数对模m-一定不同余。对任 意一个整数a,令 C={a+km:k∈Z} 则有如下定理: 定理1设m是一个正整数,则 (1)C=C的充分必要条件是a≡ b(mod n); (2)对任意的整数a,b,要么C=C,要么C∩C=φ; (3)存在m个数两两对模m互不同余,且在任意m+1个 整数中,必有两个数对模m同余 证(1)若C=C,因为b∈C.=C.,所以存在整数k, 使得b=a+m,即a≡b(modm),必要性得证。下证充分 性 设整数a,b满足关系a≡ b(mod m),则对集合C中的元素任 意c,存在整数k,使得C=a+km,由已知条件 a≡b(modm),存在整数k,使得a=b+km,于是得 C=b+(k1+k2)m,所以有c∈C,由c的任意性知CcC; 反方向的包含关系同理可证,故C=C
§2.2 剩余类与剩余系 由上一节性质 1 知，对于给定的整数模 m ，整数的同余关系 是所有整数构成的集合 上的一个等价关系，因此可以由这 个等价关系诱导一个划分，即把集合 分成 m 个两两互不相 交的集合，且同一个集合中的任意两个整数对模 m 一定同 余，而属于不同集合中的两个整数对模 m 一定不同余。对任 意一个整数 a ，令 C ={a + km: k } a 则有如下定理： 定理 1 设 m 是一个正整数，则 （1） C a = Cb 的充分必要条件是 a b(modm) ； （2） 对任意的整数 a,b ，要么 C a = Cb ，要么 C a Cb = ； （3） 存在 m 个数两两对模 m 互不同余，且在任意 m +1 个 整数中，必有两个数对模 m 同余。 证 （1）若 C a = Cb ，因为 bCb =C a ，所以存在整数 k ， 使得 b = a + km ，即 a b(modm) ，必要性得证。下证充分 性。 设整数 a,b 满足关系 a b(modm) ，则对集合 C a 中的元素任 意 c ， 存 在 整 数 1 k ， 使 得 c = a + k1m ， 由 已 知 条 件 a b(modm) ，存在整数 2 k ，使得 a = b + k2m ，于是得 c = b + (k1 + k2 )m ，所以有 Cb c ，由 c 的任意性知 C a Cb ； 反方向的包含关系同理可证，故 C a = Cb
(2)任意的两个整数a,b,要么a≡b(modm),要么 a≠ b(modm)。 如果a≡b(modm),由(1)知C。=C 如果a≠ b(mod n),用反证法。假设C∩C≠p,即存在 整数c,使得C∈C且c∈C,于是存在整数k,k2,使得 C=a+km及C=b+km,由这两个等式很容易得 a=b+(k2-km,即a≡b(modm),与条件4≠b(modm) 矛盾。因此C∩C=p (3)对于模m而言,集合{0,1,2,…,m-1}中任意两个元素 互不同余,所以由集合CC12C2,…C是m个两两互不相 交的集合,且任意一个整数,必属于其中一个集合,即它们 构成整数集合Z的一个划分。任意m+1个整数,必有两个数 属于C,C,C,…,C中的同一个集合,由(1)知它们对模 m同余 定义1每一个这样的集合C称为模m的同余类或剩余类, 个剩余类中的任意一个元素叫做该类中的代表元或剩余 一组数a,a,…a称为是模m的完全剩余系,如果对于任意 的整数a有且仅有一个整数a(1≤i≤s)与a在同一个剩余类 中 由定理1(3)知,模m的完全剩余系是存在的,且S=m以 及给定的m个整数是模m的完全剩余系的充分必要条件是 它们两两对模m不同余。事实上,一组模m的完全剩余系就
（2）任意 的两 个整 数 a,b ，要么 a b(modm) ，要么 a b(modm)。 如果 a b(modm) ，由（1）知 C a = Cb ； 如果 a b(mod m) ，用反证法。假设 C a Cb = ，即存在 整数 c ，使得 C a c 且 Cb c ，于是存在整数 1 2 k ,k ，使得 c = a + k1m 及 c = b + k2m ，由这两个等式很容易得 a = b + (k2 − k1 )m ，即 a b(modm) ，与条件 a b(mod m) 矛盾。因此 C a Cb =。 （3）对于模 m 而言，集合 {0,1,2, ,m −1} 中任意两个元素 互不同余，所以由集合 0 1 2 1 , , , , C C C C m− 是 m 个两两互不相 交的集合，且任意一个整数，必属于其中一个集合，即它们 构成整数集合 的一个划分。任意 m +1 个整数，必有两个数 属于 0 1 2 1 , , , , C C C C m− 中的同一个集合，由（1）知它们对模 m 同余。 定义 1 每一个这样的集合 C a 称为模 m 的同余类或剩余类， 一个剩余类中的任意一个元素叫做该类中的代表元或剩余。 一组数 a a a s , , , 1 2 称为是模 m 的完全剩余系，如果对于任意 的整数 a 有且仅有一个整数 a (1 i s) i 与 a 在同一个剩余类 中。 由定理 1（3）知，模 m 的完全剩余系是存在的，且 s = m 以 及给定的 m 个整数是模 m 的完全剩余系的充分必要条件是 它们两两对模 m 不同余。事实上，一组模 m 的完全剩余系就
是在模m的每个同余类中取定一个数作为代表所构成的 组数。而对于模m的一个完全剩余系a,a,…,a, C4,C.,…C就是模m的m个两两不同的剩余类,且有 Z=UC 完全剩余系的形式是多种多样的,学会在不同的问题中选取 合适的完全剩余系对于解决问题很有帮助。 般地,称O,1,2,…,m-1为模m的最小非负完全剩余系 1,2,…,m为模m的最小正完全剩余系 (m-1)-(m-2),…,-1,0为模m的最大非正完全剩余系; m,-(m-1)…-2,-1为模m的最大负完全剩余系; 当m为奇数时,-(m-1)/2,…,-10,1…、(m-1)/2为模m 的绝对值最小完全剩余系, 当m为偶数时,-m/2,…,-1,0,1,…(m-2)/2或 (m-2)/2…,-1,0,1,…,m/2为模m的绝对值最小完全剩 余系。 例1设正整数m=9,对任意整数a,集合 C={a+10k:k∈z}为模m的剩余类 0,2,46,8,10,12,14,16是模9的一个完全剩余系, 0.1,2,3,4,5,6,7,8为模9的最小非负完全剩余系; 1,2,3,4,5,6,7,8,9为模9的最小正完全剩余系 8,-7,6,-5,-4,-3,-2,-1,0为模9的最大非正完全剩余系; 9-8,-7,6,-5,-4,-3,-2,-1为模9的最大负完全剩余系
是在模 m 的每个同余类中取定一个数作为代表所构成的一 组数。而对于模 m 的一个完全剩余系 a a a s , , , 1 2 ， a a am C ,C , ,C 1 2 就是模 m 的 m 个两两不同的剩余类，且有 m i ai C =1 = 完全剩余系的形式是多种多样的，学会在不同的问题中选取 合适的完全剩余系对于解决问题很有帮助。 一般地，称 0,1,2, ,m −1 为模 m 的最小非负完全剩余系； 1,2, ,m 为模 m 的最小正完全剩余系； − (m −1),−(m − 2), ,−1,0 为模 m 的最大非正完全剩余系； − m,−(m −1), ,−2,−1 为模 m 的最大负完全剩余系； 当 m 为奇数时，− (m −1)/ 2, ,−1,0,1, ,(m −1)/ 2 为模 m 的绝对值最小完全剩余系， 当 m 为 偶 数 时 ， − m/ 2, ,−1,0,1, ,(m − 2)/ 2 或 − (m − 2)/ 2, ,−1,0,1, ,m/ 2 为模 m 的绝对值最小完全剩 余系。 例 1 设 正 整 数 m = 9 ， 对 任 意 整 数 a ， 集 合 C ={a +10k : k } a 为 模 m 的剩余类， 0,2,4,6,8,10,12,14,16 是模 9 的一个完全剩余系， 0,1,2,3,4,5,6,7,8 为模 9 的最小非负完全剩余系； 1,2,3,4,5,6,7,8,9 为模 9 的最小正完全剩余系； −8,−7,−6,−5,−4,−3,−2,−1,0 为模 9 的最大非正完全剩余系； − 9,−8,−7,−6,−5,−4,−3,−2,−1 为模 9 的最大负完全剩余系；
4,-3,-2,-1,0,1,2,3,4为模9的绝对值最小完全剩余系。 例2设a,a是模m的同一个剩余类中的任意两个整数,则有 (a1,m)=(a12,m) 证设a∈C,a,∈C。则存在整数k,k,使得 a=r+km,a2=r+km,于是有(a1,m)=(m,r), (a2,m)=(m,r),所以(a1,m)=(a12,m) 例3(染色问题)设a,m是正整数,(a,m)=1,0<a<m, 记集合M={1,2,3…,m-1}。现对集合M中的每个数i涂上 黑色或白色,要满足以下条件:(1)i和m-i要涂上同一种 颜色:(2)当i≠a时,面|a-i要涂上同一种颜色。证明: 所有的数一定都涂上同一种颜色。 证我们的想法是把要涂色的集合M扩充到全体整数,除已 知两条外另外满足:(3)属于模m的同一个剩余类中的数涂 上相同的颜色;(4)0和a要涂上同一种颜色。这样就可以对 全体整数涂色,这样的涂色应该满足如下性质 [l对任意的整数j,j和-j一定涂相同的颜色。因为对于 任意的整数j,必存在整数i,使得0≤i<m,j≡i(modm), 由(3)知j和同色;而-j=-i=m-(modm),所以由 (3)知一j和m-i同色,从而由(1)和(4)知-j和j同色。 2]对任意的整数j,j利-a同色,从而属于模a的同一个 剩余类中的数涂上相同的颜色。因为对于任意的整数j,必 存在整数i,使得0≤i<m,j≡(modm),由(3)知j和i同
− 4,−3,−2,−1,0,1,2,3,4 为模 9 的绝对值最小完全剩余系。 例2 设 1 2 a , a 是模 m 的同一个剩余类中的任意两个整数，则有 ( , ) ( , ) a1 m = a2 m 。 证 设 a1 C r ， a2 C r 。则存在整数 1 2 k ,k ，使得 a1 = r + k1m ， a2 = r + k2m ，于是有 ( , ) ( , ) 1 a m = m r ， ( , ) ( , ) 2 a m = m r ，所以 ( , ) ( , ) a1 m = a2 m 。 例 3（染色问题）设 a,m 是正整数， (a,m) =1,0 a m， 记集合 M = {1,2,3, ,m −1} 。现对集合 M 中的每个数 i 涂上 黑色或白色，要满足以下条件：（1） i和m − i 要涂上同一种 颜色；（2）当 i a 时， i和| a −i | 要涂上同一种颜色。证明： 所有的数一定都涂上同一种颜色。 证 我们的想法是把要涂色的集合 M 扩充到全体整数，除已 知两条外另外满足：（3）属于模 m 的同一个剩余类中的数涂 上相同的颜色；（4） 0和a 要涂上同一种颜色。这样就可以对 全体整数涂色，这样的涂色应该满足如下性质： [1] 对任意的整数 j ， j和− j 一定涂相同的颜色。因为对于 任意的整数 j ，必存在整数 i ，使得 0 i m, j i(modm)， 由（3）知 j和i 同色；而− j −i m − i(modm) ，所以由 （3）知− j和m −i 同色，从而由（1）和（4）知− j和j 同色。 [2] 对任意的整数 j ， j和j − a 同色，从而属于模 a 的同一个 剩余类中的数涂上相同的颜色。因为对于任意的整数 j ，必 存在整数 i ，使得 0 i m, j i(modm) ，由（3）知 j和i 同
色,而由(2)知和a-计同色,进而由[]t-a和a-i同 色推出j和-a同色;由条件(3)知,属于模m的同一个剩 余类中的数同色,因为j≡(modm),所以 (-a)≡(j-a)modm),因此j-a和i-a,从而利-a 同色。 由[和[2知,对于任意的整数j,j和+Sm+ta同色,其 中s和t为任意的整数。由条件(a,m)=1知存在整数S,t,使 得Sm+ta=1,所以+1同色,即所有整数同色。 例4设a1a2…an,b,b,…b分别是模m的两组完全剩余 系。证明:当m是偶数时, a+b,a2+b2,…an+b一定不是模m的完全剩余系 证根据完全剩余系的定义可以看出,对于模m的任意两组 完全剩余系,它们各元素之和对模m是同余的,且这和同余 O(mod m) 0+1+2+…+m-1=(m-1)m/2≡ m/2(mod m) 2 m 而a1+b+a12+b2+…+an+b≡(m-1)m≡0modm), 因为当m是偶数时,m/2≠0(modm),所以 a+b,a2+b2…an+b一定不是模m的完全剩余系。 在实际应用中,我们往往要运用另外一种剩余系的概念。 定义2设m是正整数,一个模m的剩余类叫做简化剩余类
色，而由（2）知 i和| a −i | 同色，进而由[1] i − a和| a −i | 同 色推出 j和i − a 同色；由条件（3）知，属于模 m 的同一个剩 余 类 中 的 数 同 色 ， 因 为 j i(modm) ， 所 以 (i − a) ( j − a)(modm) ，因此 j − a和i − a ，从而 j和j − a 同色。 由[1]和[2]知，对于任意的整数 j ， j和j + sm + ta 同色，其 中 s和t 为任意的整数。由条件 (a,m) =1 知存在整数 1 1 s ,t ，使 得 s1m+t 1a =1 ，所以 j和j +1 同色，即所有整数同色。 例 4 设 a a a m , , , 1 2 ，b b b m , , , 1 2 分别是模 m 的两组完全剩余 系。证明：当 m 是偶数时， a +b a +b a m +b m , , , 1 1 2 2 一定不是模 m 的完全剩余系。 证 根据完全剩余系的定义可以看出，对于模 m 的任意两组 完全剩余系，它们各元素之和对模 m 是同余的，且这和同余 于 + + + + − − m m m m m m m m / 2(mod ) 2 | 0(mod ) 2 | 0 1 2 1 ( 1) / 2 ， 而 ( 1) 0(mod ) a1 +b1 + a2 +b2 ++ a m +b m m− m m ， 因为当 m 是 偶 数 时 ， m/ 2 0(modm) ，所以 a +b a +b a m +b m , , , 1 1 2 2 一定不是模 m 的完全剩余系。 在实际应用中，我们往往要运用另外一种剩余系的概念。 定义 2 设 m 是正整数，一个模 m 的剩余类叫做简化剩余类