文档介绍：§
由上一节性质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)模的任意一组简化