§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 的剩余类叫做简化剩余类
如果该类中存在一个与m互素的剩余。在模m的所有不同简 化剩余类中,从每个类中任取一个数组成的整数的集合叫做 是模m的简化剩余系。同上一样可以得到最小正简化剩余 系、最大负简化剩余系、绝对值最小简化剩余系等概念。 由例2知简化剩余类的定义与代表元的选取无关,如果令 0(m)为集合{1,2,…,m-1}中与m互素的所有整数的个数, 则q(m)为模m简化剩余系中元素的个数,称之为欧拉函数。 当m为素数p时,很容易看出此时有 qp(p)=p-1。 从定义可以看出,模m的一组完全剩余系中所有和m互素的 整数组成模m的一组简化剩余系。此外,任意给定Q(m)个 和m互素的整数,只要两两对模m不同余,它们就组成模m 的一组简化剩余系。 例5设m≥3,证明: (1)模m的任意一组简化剩余系的所有元素之和对模m必同 余于零 (2)模m的最小正简化剩余系的各数之和等于mp(m)/2 证首先证明(2)成立。设a2a2…a是所有小于m/2且和 m互素的正整数,则有 m/2<m-a<m.且(m-a,m)=1、i=12…,s 并且对于任意一个正整数a,如果它满足 m/2<a<m,且(a,m)=1
如果该类中存在一个与 m 互素的剩余。在模 m 的所有不同简 化剩余类中，从每个类中任取一个数组成的整数的集合叫做 是模 m 的简化剩余系。同上一样可以得到最小正简化剩余 系、最大负简化剩余系、绝对值最小简化剩余系等概念。 由例 2 知简化剩余类的定义与代表元的选取无关，如果令 (m) 为集合 1,2, ,m −1 中与 m 互素的所有整数的个数， 则 (m) 为模 m 简化剩余系中元素的个数，称之为欧拉函数。 当 m 为素数 p 时，很容易看出此时有 ( p) = p −1。 从定义可以看出，模 m 的一组完全剩余系中所有和 m 互素的 整数组成模 m 的一组简化剩余系。此外，任意给定 (m) 个 和 m 互素的整数，只要两两对模 m 不同余，它们就组成模 m 的一组简化剩余系。 例 5 设 m 3 ，证明： （1）模 m 的任意一组简化剩余系的所有元素之和对模 m 必同 余于零； （2）模 m 的最小正简化剩余系的各数之和等于 m(m)/ 2。 证 首先证明（2）成立。设 a a a s , , 1 2 是所有小于 m/ 2 且和 m 互素的正整数，则有 m m a m m a m i s i i / 2 − ,且（ − , ）=1, =1,2, , ， 并且对于任意一个正整数 a ，如果它满足 m/ 2 a m,且（a,m）=1
则有0<m-a<m/2.且(m-a,m)=1,因此一定存在 个正整数a,1≤i≤s,使得m-a=a,即a=m-a,所以 a.m-a.nnm-d m-d 构成模m的最小正简化剩余系,所以得q(m)=2s,且 a+a12+…+a,+m-a,+…+m-a=m=m0(m)/2。 而(1)由(2)很容易得到。 定理2设m是正整数,a是满足(a2,m)=1的整数,b是任 意整数。若κ遍历模m的一个完全剩余系,则ax+b也遍历 模m的一个完全剩余系;若x遍历模m的一个简化剩余系, 则a也遍历模m的一个简化剩余系。 证根据定理1和定义,我们只需证明:当 aa 是模m的一个完全剩余系时,m个整数 aa+b,aa+b…aa+b 模m两两互不同余。反证法。假设其中存在两个整数 a,a,(≠j),使得 aa+b=aa + b(mod m) 因为(a,m)=1,所以由2.1性质2(1)和(5)可知 a=a(modm),即a,a,属于同一个剩余类,这与 a1,a2,…,a是模m的一个完全剩余系矛盾。因此,ax+b也 遍历模m的一个完全剩余系。对于简化剩余系,我们同样可 以证明Q(m)个整数
则有 0 m − a m/ 2,且（m − a,m）=1 ，因此一定存在一 个正整数 a i s i ,1 ，使得 m− a = ai ，即 a = m− ai ，所以 1 2 1 1 a ,a , a s ,m− a s ,m− a s− , ,m− a 构成模 m 的最小正简化剩余系，所以得 (m) = 2s ，且 a1 + a2 ++ a s + m − a s ++ m− a1 = ms = m(m)/ 2。 而（1）由（2）很容易得到。 定理 2 设 m 是正整数， a 是满足 (a,m) =1 的整数， b 是任 意整数。若 x 遍历模 m 的一个完全剩余系，则 ax + b 也遍历 模 m 的一个完全剩余系；若 x 遍历模 m 的一个简化剩余系， 则 ax 也遍历模 m 的一个简化剩余系。 证 根据定理 1 和定义，我们只需证明：当 a a a m , , , 1 2 是模 m 的一个完全剩余系时， m 个整数 aa1 +b,aa2 +b, ,aa m +b 模 m 两两互不同余。反证法。假设其中存在两个整数 a ,a (i j) i j ，使得 aa b aa b(modm) i + j + 因 为 (a,m) =1 ，所以由 2.1 性 质 2(1) 和 (5) 可 知 a a (modm) i j ， 即 ai aj , 属 于 同 一 个 剩 余 类 ， 这 与 a a a m , , , 1 2 是模 m 的一个完全剩余系矛盾。因此， ax + b 也 遍历模 m 的一个完全剩余系。对于简化剩余系，我们同样可 以证明 (m) 个整数
1,aa2,…, 模m两两互不同余,且由(a,m)=(an,m)=1得(aa,m)=1, 从而组成模m的一个简化剩余系 定理2表明:只要(a,m)=1,我们就可以找到这样的模m的 完全剩余系和简化剩余系,它们的元素都是a的倍数;而当 (a,m)>1时,这是一定不可能的。如:5·0.5·1,…,5·7是模 8的完全剩余系,5·1,5·3,5·5,5:7是模8的简化剩余系。但 是2·0,2·1…,2·7不是模8的完全剩余系 2·1,2·3,2·5,2·7也不是模8的简化剩余系 对于不同模之间的剩余系,我们有如下结论: 定理3设m,H是两个互素的正整数,如果x,y分别遍历模 m,n的完全(简化)剩余系,则nx+my遍历模m的完全(简 化)剩余系。 证对于完全剩余系,若x1,x2…x和yy2…y分别是 模m和n的一组完全剩余系,则集合 {nx+my,i=1,2,…,m,yj=1,2,…,n}一共有mm个元素, 所以只需证明它们关于模mm两两互不同余即可。反证法, 若存在整数x,x,和y,y满足 nx,+my,= nx, +my, (mod mn) 则由上一节性质2(7)有 nx+my,≡nx,+my(modm) 和
1 2 ( ) , , , aa aa aa m 模 m 两两互不同余，且由 (a,m) = (ai ,m) =1 得 (aai ,m) =1， 从而组成模 m 的一个简化剩余系。 定理 2 表明：只要 (a,m) =1 ，我们就可以找到这样的模 m 的 完全剩余系和简化剩余系，它们的元素都是 a 的倍数；而当 (a,m) 1 时，这是一定不可能的。如： 50,51, ,57 是模 8 的完全剩余系， 51,53,55,5 7 是模 8 的简化剩余系。但 是 20,21, ,27 不 是 模 8 的 完 全 剩 余 系 ， 21,23,25,2 7 也不是模 8 的简化剩余系。 对于不同模之间的剩余系，我们有如下结论： 定理 3 设 m,n 是两个互素的正整数，如果 x, y 分别遍历模 m,n 的完全（简化）剩余系，则 nx + my 遍历模 mn 的完全（简 化）剩余系。 证 对于完全剩余系，若 m x , x , , x 1 2 和 n y , y , , y 1 2 分别是 模 m和n 的一组完全剩余系，则集 合 {nx my | i 1,2, ,m, j 1,2, ,n} i + j = = 一共有 mn 个元素， 所以只需证明它们关于模 mn 两两互不同余即可。反证法， 若存在整数 i j x , x 和 k l y , y 满足 nx my nx my (mod mn) i + k j + l ， 则由上一节性质 2（7）有 nx my nx my (mod m) i + k j + l 和
nx,+my,=nx +my (modn) 进而有 nx≡nx(modm) 和 my=my,(modn) 因为m,n互素,所以由同余的性质2(5)可得x,x和y2y分 别关于模m和模n同余,这与x,x2…x和y,y2,…,y分别 是模m和n的一组完全剩余系矛盾 对于简化剩余系,因为(m,n)=1,所以 (nx+my, mn)=le (nx+my,m)=1÷(nx,m)=1<→(x,m) (mx+mn)=1(m;m)=1(ym)=1 即(x,m)=1且(y,n)=1÷→(mx+m,mm)=1,充分性说明 模mm的任意一个简化剩余可以表示成nx+my (x,m)=1且(y,n)=1)这种形式,必要性说明任意一个能 表示成nx+my((x,m)=1且(y,n)=1)这种形式的剩余类 定是简化剩余类。因此nx+my遍历模mm的简化剩余系。 例6分别用模4和模5的完全剩余系和简化剩余系来表示模 20的完全剩余系和简化剩余系。 解取模4的一组完全剩余系为0,1,2,3,取模5的一组完全 剩余系为0,12,3,4,则由定理3得模20的一组完全剩余系为 04,8,12,16,5,9,13,17,21,10,14,18,22,26,15,19,23,27,31
nx my nx my (mod n) i + k j + l 进而有 nx nx (modm) i j 和 my my (modn) k l 因为 m,n 互素，所以由同余的性质 2（5）可得 i j x , x 和 k l y , y 分 别关于模 m 和模 n 同余，这与 m x , x , , x 1 2 和 n y , y , , y 1 2 分别 是模 m和n 的一组完全剩余系矛盾。 对于简化剩余系，因为 (m,n) =1 ，所以 (nx + my,mn) =1 + = = = + = = = ( , ) 1 ( , ) 1 ( , ) 1 ( , ) 1 ( , ) 1 ( , ) 1 nx my n my n y n nx my m nx m x m 即 (x,m) =1且(y,n) =1 (nx + my,mn) =1 ，充分性说明 模 mn 的任意一个简化剩余可以表示成 nx + my （ (x,m) =1且(y,n) =1 ）这种形式，必要性说明任意一个能 表示成 nx + my （ (x,m) =1且(y,n) =1 ）这种形式的剩余类 一定是简化剩余类。因此 nx + my 遍历模 mn 的简化剩余系。 例 6 分别用模 4 和模 5 的完全剩余系和简化剩余系来表示模 20 的完全剩余系和简化剩余系。 解 取模 4 的一组完全剩余系为 0,1,2,3，取模 5 的一组完全 剩余系为 0,1,2,3,4，则由定理 3 得模 20 的一组完全剩余系为 0,4,8,12,16,5,9,13,17,21,10,14,18,22,26,15,19,23,27,31
取模4的一组简化剩余系为1,3,取模5的一组简化剩余系 为1,2,34,则由定理3得模20的一组完全剩余系为 9,13,17,21,19,23,27,31 由定理3,我们很容易得到如下关于欧拉函数的一个性质定 理 定理4若正整数m,n满足(m,n)=1,则有 q(m)=(m)p(m)。 证根据定理3,当x,y分别遍历模m,n的简化剩余系时, 分别有o(m),gp(n)个整数,因此集合{nx+mylx,y分别遍历 模m,n的简化剩余系}共有o(m)p(n)个元素且为模mm的 组简化剩余系,而模mm的一组简化剩余系应该有op(mm)个 整数,所以 q(m)=0(m)(n) 结论成立。 有了定理4,下面我们来研究欧拉函数的计算。 定理5设p为素数,a为正整数,则有 qp(p")=p-p“=p"(1 进一步,若正整数n有标准因数分解式 n=∏p=p"p2…P 则有
取模 4 的一组简化剩余系为 1,3，取模 5 的一组简化剩余系 为 1,2,3,4，则由定理 3 得模 20 的一组完全剩余系为 9,13,17,21,19,23,27,31。 由定理 3，我们很容易得到如下关于欧拉函数的一个性质定 理。 定理 4 若正整数 m,n 满足 (m,n) =1 ，则有 (mn) = (m)(n)。 证 根据定理 3，当 x, y 分别遍历模 m,n 的简化剩余系时， 分别有 (m),(n) 个整数，因此集合{ nx + my | x, y 分别遍历 模 m,n 的简化剩余系}共有 (m)(n) 个元素且为模 mn 的一 组简化剩余系，而模 mn 的一组简化剩余系应该有 (mn) 个 整数，所以 (mn) = (m)(n) 结论成立。 有了定理 4，下面我们来研究欧拉函数的计算。 定理 5 设 p 为素数， a 为正整数，则有 ) 1 ( ) (1 1 p p p p p a a a a = − = − − ， 进一步，若正整数 n 有标准因数分解式 ak k a p n a a n p p p p 1 2 2 | = = 1 则有