由于同余是一个整数环上的等价关系,我们来建立同余意义下“等价类”的概念——同余类。
定义[]
对于确定整数
而言,所有模
同余于
的数,构成一个集合,称作一个模
同余类,即

如模

同余于

的同余类就是

这个集合。在同余的意义下,

和所有模

同余于

的元素所得的结果是一样的,因此可以说,

把这些数都“代表”了。
这实际上是对整数集全体
做了一个划分,最简单的一个划分就是模
的同余类——将整数分为奇数与偶数:

划分有限性[]
两个模
的同余类
,因此模
同余类有
个,它们是
。
完全剩余系[]
若从模
的所有不同同余类中,各取出一个元素组成的集合,称为模
的一个完全剩余系或完全代表系,简称完系,如模
的完全剩余系就是
,其中
、
、
、
、
是任意整数。很多时候讨论模
的完全剩余系时,都讨论由
到
(即任意数除
时,在一般定义下所有可能出现的余数)这几个数所组成的完全剩余系,因为不管讨论哪个剩余系,很多定理都会有相同的结果,因此很多时候讨论模
的完全剩余系时,就是讨论
这个剩余系。
性质[]
设
,若
是
的一个完系,那么
也是
的一个完系。
这意味着完系可以在整数集合上“放缩”和“平移”。
缩同余类与缩代表系[]
对于
而言,若
,那么模
的一个同余类
中的所有整数都与
互素,这样的同余类叫做模
的缩同余类。模
的缩同余类的个数是
中与
互素的元素个数。
像同余类与完系那样,从每个模
的缩同余类中取一个代表,这些代表组成的集合叫做模
的一个缩代表系,简称缩系。例如,
是模
的一个缩系,而
是模
的一个缩系。由于素数
与所有比它小的正整数都互素,因此,模素数
的缩系就是它的完系。
所有模
的缩系中都有元素
。
在欧拉函数中,我们会对模
的缩系的元素个数做一个具体的刻画。
性质[]
设
,若
是
的一个缩系,那么
也是
的一个缩系。
这意味着完系可以在整数集合上“放缩”,但一般不能“平移”。
上下节[]