同餘類

由於同餘是一個整數環上的等價關係，我們來建立同餘意義下“等價類”的概念——同餘類。

定義

對於確定整數$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$的一個縮系。

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

上下節

• 上一節：同餘
• 下一節：同餘類的代數結構