§2.2剩余类与剩余系由上一节性质1知，对于给定的整数模，整数的同余关系是所有整数构成的集合上的一个等价关系，因此可以由这个等价关系诱导一个划分，即把集合分成个两两互不相交的集合，且同一个集合中的任意两个整数对模一定同余，而属于不同集合中的两个整数对模一定不同余。对任意一个整数，令
则有如下定理：
定理1 设是一个正整数，则
（1） 的充分必要条件是；
（2） 对任意的整数，要么，要么；
（3） 存在个数两两对模互不同余，且在任意个整数中，必有两个数对模同余。
证 （1）若，因为，所以存在整数，使得，即，必要性得证。下证充分性。
设整数满足关系，则对集合中的元素任意，存在整数，使得，由已知条件，存在整数，使得，于是得
，所以有，由的任意性知；反方向的包含关系同理可证，故。
（2）任意的两个整数，要么，要么。
如果，由（1）知；
如果，用反证法。假设，即存在整数，使得且，于是存在整数，使得及，由这两个等式很容易得
，即，与条件矛盾。因此。
（3）对于模而言，集合中任意两个元素互不同余，所以由集合是个两两互不相交的集合，且任意一个整数，必属于其中一个集合，即它们构成整数集合的一个划分。任意个整数，必有两个数属于中的同一个集合，由（1）知它们对模同余。
定义1 每一个这样的集合称为模的同余类或剩余类，一个剩余类中的任意一个元素叫做该类中的代表元或剩余。一组数称为是模的完全剩余系，如果对于任意的整数有且仅有一个整数与在同一个剩余类中。
由定理1（3）知，模的完全剩余系是存在的，且以及给定的个整数是模的完全剩余系的充分必要条件是它们两两对模不同余。事实上，一组模的完全剩余系就是在模的每个同余类中取定一个数作为代表所构成的一组数。而对于模的一个完全剩余系，就是模的个两两不同的剩余类，且有
完全剩余系的形式是多种多样的，学会在不同的问题中选取合适的完全剩余系对于解决问题很有帮助。
一般地，称为模的最小非负完全剩余系；
为模的最小正完全剩余系；
为模的最大非正完全剩余系；
为模的最大负完全剩余系；
当为奇数时，为模的绝对值最小完全剩余系，
当为偶数时，或为模的绝对值最小完全剩余系。
例1 设正整数，对任意整数，集合为模的剩余类，是模的一个完全剩余系，
为模的最小非负完全剩余系；
为模的最小正完全剩余系；
为模的最大非正完全剩余系；
为模的最大负完全剩余系；
为模的绝对值最小完全剩余系。
设是模的同一个剩余类中的任意两个整数，则有
。
证 设，。则存在整数，使得，，于是有，，所以。
例3（染色问题）设是正整数，，记集合。现对集合中的每个数涂上黑色或白色，要满足以下条件：（1）要涂上同一种颜色；（2）当时，要涂上同一种颜色。证明：所有的数一定都涂上同一种颜色。
证 我们的想法是把要涂色的集合扩充到全体整数，除已知两条外另外满足：（3）属于模的同一个剩余类中的数涂上相同的颜色；（4）要涂上同一种颜色。这样就可以对全体整数涂色，这样的涂色应该满足如下性质：
[1] 对任意的整数，一定涂相同的颜色。因为对于任意的整数，必存在整数，使得，由（3）知同色；而，所以由（3）知同色，从而由（1）和（4）知同色。
[2] 对任意的整数，同色，从而属于模的同一个剩余类中的数涂上相同的颜色。因为对于任意的整数，必存在整数，使得，由（3）知同色，而由（2）知同色，进而由[1]同色推出同色；由条件（3）知，属于模的同一个剩余类中的数同色，因为，所以，因此，从而同色。
由[1]和[2]知，对于任意的整数，同色，其中为任意的整数。由条件知存在整数，使得，所以同色，即所有整数同色。
例4 设，分别是模的两组完全剩余系。证明：当是偶数时，
一定不是模的完全剩余系。
证 根据完全剩余系的定义可以看出，对于模的任意两组完全剩余系，它们各元素之和对模是同余的，且这和同余于
，
而，因为当是偶数时，，所以一定不是模的完全剩余系。
在实际应用中，我们往往要运用另外一种剩余系的概念。
定义2 设是正整数，一个模的剩余类叫做简化剩余类，如果该类中存在一个与互素的剩余。在模的所有不同简化剩余类中，从每个类中任取一个数组成的整数的集合叫做是模的简化剩余系。同上一样可以得到最小正简化剩余系、最大负简化剩余系、绝对值最小简化剩余系等概念。
由例2知简化剩余类的定义与代表元的选取无关，如果令为集合中与互素的所有整数的个数，则为模简化剩余系中元素的个数，称之为欧拉函数。当为素数时，很容易看出此时有
。
从定义可以看出，模的一组完全剩余系中所有和互素的整数组成模的一组简化剩余系。此外，任意给定个和互素的整数，只要两两对模不同余，它们就组成模的一组简化剩余系。
例5 设，证明：
（1）模的任意一组简化剩余系的所有元素之和对模必同余于零；
（2）模的最小正简化剩余系的各数之和等于。
证 首先证明（2）成立。设是所有小于且和互素的正整数，则有
，
并且对于任意一个正整数，如果它满足
，
则有，因此一定存在一个正整数，使得，即，所以
构成模的最小正简化剩余系，所以得，且
。
而（1）由（2）很容易得到。
定理2 设是正整数，是满足的整数，是任意整数。若遍历模的一个完全剩余系，则也遍历模的一个完全剩余系；若遍历模的一个简化剩余系，则也遍历模的一个简化剩余系。
证 根据定理1和定义，我们只需证明：当
是模的一个完全剩余系时，个整数
模两两互不同余。反证法。假设其中存在两个整数，使得
因为，所以由2.1性质2(1)和(5)可知，即属于同一个剩余类，这与是模的一个完全剩余系矛盾。因此，也遍历模的一个完全剩余系。对于简化剩余系，我们同样可以证明个整数
模两两互不同余，且由得，从而组成模的一个简化剩余系。
定理2表明：只要，我们就可以找到这样的模的完全剩余系和简化剩余系，它们的元素都是的倍数；而当时，这是一定不可能的。如：是模8的完全剩余系，是模8的简化剩余系。但是不是模8的完全剩余系，也不是模8的简化剩余系。
对于不同模之间的剩余系，我们有如下结论：
定理3 设是两个互素的正整数，如果分别遍历模的完全（简化）剩余系，则遍历模的完全（简化）剩余系。
证 对于完全剩余系，若和分别是模的一组完全剩余系，则集合一共有个元素，所以只需证明它们关于模两两互不同余即可。反证法，若存在整数和满足
，
则由上一节性质2（7）有
和
进而有
和
因为互素，所以由同余的性质2（5）可得和分别关于模和模同余，这与和分别是模的一组完全剩余系矛盾。
对于简化剩余系，因为，所以
即，充分性说明模的任意一个简化剩余可以表示成（）这种形式，必要性说明任意一个能表示成（）这种形式的剩余类一定是简化剩余类。因此遍历模的简化剩余系。
例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,3,4，则由定理3得模20的一组完全剩余系为9,13,17,21,19,23,27,31。
由定理3，我们很容易得到如下关于欧拉函数的一个性质定理。
定理4 若正整数满足,则有
。
证 根据定理3，当分别遍历模的简化剩余系时，分别有个整数，因此集合{|分别遍历模的简化剩余系}共有个元素且为模的一组简化剩余系，而模的一组简化剩余系应该有个整数，所以
结论成立。
有了定理4，下面我们来研究欧拉函数的计算。
定理5 设为素数，为正整数，则有
，
进一步，若正整数有标准因数分解式
则有
。
证 模的最小非负完全剩余系为
共有个整数，其中与模不互素的整数为
共个整数，因此模的简化剩余系的元素个数为，即
。
结合定理4，我们就可以得到任何一个具有标准因数分解式的正整数的欧拉函数的计算公式
。
由定理4和定理5还可以推出定理6 对于任意正整数有
。
证 方法一：
若，为素数，则有
若，且对于正整数，有
为了简单，下面求和符号的因数指的都是正因数，且指的是，则有
因此由归纳法容易得到结论成立。
方法二：
对正整数集合按其和的最大公因数分类，
，
则有
由整除的性质
即集合的元素个数为
由集合的定义可知，对于任意两个整数，，所以
。
设正整数，试计算且按照定理6对集合进行分类。
解 因为，所以由定理5得
84的正因数有1，2，3，4，6，7，12，14，21，28，42，84，按照定理6，集合的分类为
例8 设，。证明：，等号当且时成立。
证 因为，所以对于任意整数，若，必有。在个相邻整数中，与不互素的数有个，这些数同样与不互素。所以把集合分成个集合，每个集合由个连续的整数构成，则每个集合中与不互素的元素个数大于等于，所以有
，
等号成立当且仅当。
则有如下定理：
定理1 设是一个正整数，则
（1） 的充分必要条件是；
（2） 对任意的整数，要么，要么；
（3） 存在个数两两对模互不同余，且在任意个整数中，必有两个数对模同余。
证 （1）若，因为，所以存在整数，使得，即，必要性得证。下证充分性。
设整数满足关系，则对集合中的元素任意，存在整数，使得，由已知条件，存在整数，使得，于是得
，所以有，由的任意性知；反方向的包含关系同理可证，故。
（2）任意的两个整数，要么，要么。
如果，由（1）知；
如果，用反证法。假设，即存在整数，使得且，于是存在整数，使得及，由这两个等式很容易得
，即，与条件矛盾。因此。
（3）对于模而言，集合中任意两个元素互不同余，所以由集合是个两两互不相交的集合，且任意一个整数，必属于其中一个集合，即它们构成整数集合的一个划分。任意个整数，必有两个数属于中的同一个集合，由（1）知它们对模同余。
定义1 每一个这样的集合称为模的同余类或剩余类，一个剩余类中的任意一个元素叫做该类中的代表元或剩余。一组数称为是模的完全剩余系，如果对于任意的整数有且仅有一个整数与在同一个剩余类中。
由定理1（3）知，模的完全剩余系是存在的，且以及给定的个整数是模的完全剩余系的充分必要条件是它们两两对模不同余。事实上，一组模的完全剩余系就是在模的每个同余类中取定一个数作为代表所构成的一组数。而对于模的一个完全剩余系，就是模的个两两不同的剩余类，且有
完全剩余系的形式是多种多样的，学会在不同的问题中选取合适的完全剩余系对于解决问题很有帮助。
一般地，称为模的最小非负完全剩余系；
为模的最小正完全剩余系；
为模的最大非正完全剩余系；
为模的最大负完全剩余系；
当为奇数时，为模的绝对值最小完全剩余系，
当为偶数时，或为模的绝对值最小完全剩余系。
例1 设正整数，对任意整数，集合为模的剩余类，是模的一个完全剩余系，
为模的最小非负完全剩余系；
为模的最小正完全剩余系；
为模的最大非正完全剩余系；
为模的最大负完全剩余系；
为模的绝对值最小完全剩余系。
设是模的同一个剩余类中的任意两个整数，则有
。
证 设，。则存在整数，使得，，于是有，，所以。
例3（染色问题）设是正整数，，记集合。现对集合中的每个数涂上黑色或白色，要满足以下条件：（1）要涂上同一种颜色；（2）当时，要涂上同一种颜色。证明：所有的数一定都涂上同一种颜色。
证 我们的想法是把要涂色的集合扩充到全体整数，除已知两条外另外满足：（3）属于模的同一个剩余类中的数涂上相同的颜色；（4）要涂上同一种颜色。这样就可以对全体整数涂色，这样的涂色应该满足如下性质：
[1] 对任意的整数，一定涂相同的颜色。因为对于任意的整数，必存在整数，使得，由（3）知同色；而，所以由（3）知同色，从而由（1）和（4）知同色。
[2] 对任意的整数，同色，从而属于模的同一个剩余类中的数涂上相同的颜色。因为对于任意的整数，必存在整数，使得，由（3）知同色，而由（2）知同色，进而由[1]同色推出同色；由条件（3）知，属于模的同一个剩余类中的数同色，因为，所以，因此，从而同色。
由[1]和[2]知，对于任意的整数，同色，其中为任意的整数。由条件知存在整数，使得，所以同色，即所有整数同色。
例4 设，分别是模的两组完全剩余系。证明：当是偶数时，
一定不是模的完全剩余系。
证 根据完全剩余系的定义可以看出，对于模的任意两组完全剩余系，它们各元素之和对模是同余的，且这和同余于
，
而，因为当是偶数时，，所以一定不是模的完全剩余系。
在实际应用中，我们往往要运用另外一种剩余系的概念。
定义2 设是正整数，一个模的剩余类叫做简化剩余类，如果该类中存在一个与互素的剩余。在模的所有不同简化剩余类中，从每个类中任取一个数组成的整数的集合叫做是模的简化剩余系。同上一样可以得到最小正简化剩余系、最大负简化剩余系、绝对值最小简化剩余系等概念。
由例2知简化剩余类的定义与代表元的选取无关，如果令为集合中与互素的所有整数的个数，则为模简化剩余系中元素的个数，称之为欧拉函数。当为素数时，很容易看出此时有
。
从定义可以看出，模的一组完全剩余系中所有和互素的整数组成模的一组简化剩余系。此外，任意给定个和互素的整数，只要两两对模不同余，它们就组成模的一组简化剩余系。
例5 设，证明：
（1）模的任意一组简化剩余系的所有元素之和对模必同余于零；
（2）模的最小正简化剩余系的各数之和等于。
证 首先证明（2）成立。设是所有小于且和互素的正整数，则有
，
并且对于任意一个正整数，如果它满足
，
则有，因此一定存在一个正整数，使得，即，所以
构成模的最小正简化剩余系，所以得，且
。
而（1）由（2）很容易得到。
定理2 设是正整数，是满足的整数，是任意整数。若遍历模的一个完全剩余系，则也遍历模的一个完全剩余系；若遍历模的一个简化剩余系，则也遍历模的一个简化剩余系。
证 根据定理1和定义，我们只需证明：当
是模的一个完全剩余系时，个整数
模两两互不同余。反证法。假设其中存在两个整数，使得
因为，所以由2.1性质2(1)和(5)可知，即属于同一个剩余类，这与是模的一个完全剩余系矛盾。因此，也遍历模的一个完全剩余系。对于简化剩余系，我们同样可以证明个整数
模两两互不同余，且由得，从而组成模的一个简化剩余系。
定理2表明：只要，我们就可以找到这样的模的完全剩余系和简化剩余系，它们的元素都是的倍数；而当时，这是一定不可能的。如：是模8的完全剩余系，是模8的简化剩余系。但是不是模8的完全剩余系，也不是模8的简化剩余系。
对于不同模之间的剩余系，我们有如下结论：
定理3 设是两个互素的正整数，如果分别遍历模的完全（简化）剩余系，则遍历模的完全（简化）剩余系。
证 对于完全剩余系，若和分别是模的一组完全剩余系，则集合一共有个元素，所以只需证明它们关于模两两互不同余即可。反证法，若存在整数和满足
，
则由上一节性质2（7）有
和
进而有
和
因为互素，所以由同余的性质2（5）可得和分别关于模和模同余，这与和分别是模的一组完全剩余系矛盾。
对于简化剩余系，因为，所以
即，充分性说明模的任意一个简化剩余可以表示成（）这种形式，必要性说明任意一个能表示成（）这种形式的剩余类一定是简化剩余类。因此遍历模的简化剩余系。
例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,3,4，则由定理3得模20的一组完全剩余系为9,13,17,21,19,23,27,31。
由定理3，我们很容易得到如下关于欧拉函数的一个性质定理。
定理4 若正整数满足,则有
。
证 根据定理3，当分别遍历模的简化剩余系时，分别有个整数，因此集合{|分别遍历模的简化剩余系}共有个元素且为模的一组简化剩余系，而模的一组简化剩余系应该有个整数，所以
结论成立。
有了定理4，下面我们来研究欧拉函数的计算。
定理5 设为素数，为正整数，则有
，
进一步，若正整数有标准因数分解式
则有
。
证 模的最小非负完全剩余系为
共有个整数，其中与模不互素的整数为
共个整数，因此模的简化剩余系的元素个数为，即
。
结合定理4，我们就可以得到任何一个具有标准因数分解式的正整数的欧拉函数的计算公式
。
由定理4和定理5还可以推出定理6 对于任意正整数有
。
证 方法一：
若，为素数，则有
若，且对于正整数，有
为了简单，下面求和符号的因数指的都是正因数，且指的是，则有
因此由归纳法容易得到结论成立。
方法二：
对正整数集合按其和的最大公因数分类，
，
则有
由整除的性质
即集合的元素个数为
由集合的定义可知，对于任意两个整数，，所以
。
设正整数，试计算且按照定理6对集合进行分类。
解 因为，所以由定理5得
84的正因数有1，2，3，4，6，7，12，14，21，28，42，84，按照定理6，集合的分类为
例8 设，。证明：，等号当且时成立。
证 因为，所以对于任意整数，若，必有。在个相邻整数中，与不互素的数有个，这些数同样与不互素。所以把集合分成个集合，每个集合由个连续的整数构成，则每个集合中与不互素的元素个数大于等于，所以有
，
等号成立当且仅当。
