同馀类

由于同馀是一个整数环上的等价关系，我们来建立同馀意义下“等价类”的概念——同馀类。

定义

对于确定整数$m$而言，所有模$m$同馀于$a$的数，构成一个集合，称作一个模$m$同馀类，即 $$\bar{a} = \{ n \in \Z: n \equiv a \pmod{m} \}$$ 如模$7$同馀于$3$的同馀类就是$\bar{3} = \left\{ \cdots, -25, -18, -11, -4, 3, 10, 17, 24, 31, \cdots \right\}$这个集合。在同馀的意义下，$3$和所有模$7$同馀于$3$的元素所得的结果是一样的，因此可以说，$3$把这些数都“代表”了。

这实际上是对整数集全体$\mathbb{Z}$做了一个划分，最简单的一个划分就是模$2$的同馀类——将整数分为奇数与偶数：
$$\begin{align} \bar{0} & = \{ \cdots, -4, -2, 0, 2, 4, \cdots \} \\ \bar{1} & = \{ \cdots, -3, -1, 1, 3, 5, \cdots \} \end{align}$$

划分有限性

两个模$m$的同馀类$\bar{a} = \bar{b} \iff a \equiv b \pmod{m}$，因此模$m$同馀类有$m$个，它们是$\bar{0}, \bar{1}, \bar{2}, \cdots, \overline{m-1}$。

完全剩馀系

若从模$m$的所有不同同馀类中，各取出一个元素组成的集合，称为模$m$的一个完全剩馀系或完全代表系，简称完系，如模$5$的完全剩馀系就是$\left\{5m_0, 5m_1+1,5m_2+2, 5m_3+3, 5m_4+4 \right\}$，其中$m_0$、$m_1$、$m_2$、$m_3$、$m_4$是任意整数。很多时候讨论模$m$的完全剩馀系时，都讨论由$0$到$m - 1$(即任意数除$m$时，在一般定义下所有可能出现的馀数)这几个数所组成的完全剩馀系，因为不管讨论哪个剩馀系，很多定理都会有相同的结果，因此很多时候讨论模$5$的完全剩馀系时，就是讨论$\left\{0,1,2,3,4\right\}$这个剩馀系。

性质

设$a, b \in \Z$，若$\left\{c_1, c_2, c_3, \cdots, c_m \right\}$是$m$的一个完系，那么$\left\{a c_1 + b, a c_2 + b, a c_3 + b, \cdots, a c_m + b \right\}$也是$m$的一个完系。

这意味著完系可以在整数集合上“放缩”和“平移”。

缩同馀类与缩代表系

对于$m$而言，若$(a, m) = 1$，那么模$m$的一个同馀类$\bar{a}$中的所有整数都与$m$互素，这样的同馀类叫做模$m$的缩同馀类。模$m$的缩同馀类的个数是$1, 2, \cdots, m-1$中与$m$互素的元素个数。

像同馀类与完系那样，从每个模$m$的缩同馀类中取一个代表，这些代表组成的集合叫做模$m$的一个缩代表系，简称缩系。例如，$\{ 1, 3, 5, 7 \}$是模$8$的一个缩系，而$\{1,2,3,4\}$是模$5$的一个缩系。由于素数$p$与所有比它小的正整数都互素，因此，模素数$p$的缩系就是它的完系。 所有模$m > 1$的缩系中都有元素$\bar{1}$。

在欧拉函数中，我们会对模$n$的缩系的元素个数做一个具体的刻画。

性质

设$a \in \Z$，若$\left\{c_1, c_2, c_3, \cdots, c_d \right\}$是$m$的一个缩系，那么$\left\{a c_1, a c_2, a c_3, \cdots, a c_d \right\}$也是$m$的一个缩系。

这意味著完系可以在整数集合上“放缩”，但一般不能“平移”。

上下节

• 上一节：同馀
• 下一节：同馀类的代数结构