前置的抽象代数知识（需要这些知识的将被标上「△」，如果不会的话不看这部分其实也大差不差）
等价类与商集
代数系统的置换性质和同余关系
环
【△同余是一个同余关系】$\forall m \in \Z^+$（作为模数），我们已经知道二元关系同余 $\equiv_m$ 是 $\Z$ 上的等价关系。事实上它还对整数加法 $+$ 和整数乘法 $\times$ 具有置换性质，因而是环 $\langle \Z, +, \times \rangle$ 上的同余关系。
证明
$\equiv_m$ 对 $+$ 的置换性根据「两同余式作和仍保持同余」性质立即得到：
$\forall m \in \Z^+$，$\forall a_1, b_1, a_2, b_2 \in \Z$，如果 $a_1 \equiv b_1 \pmod m$ 且 $a_2 \equiv b_2 \pmod m$，那么根据 $a_1 + a_2 \equiv b_1 + b_2 \pmod m$。
$\equiv_m$ 对 $\times$ 的置换性根据「两同余式作积仍保持同余」性质立即得到：
$\forall m \in \Z^+$，$\forall a_1, b_1, a_2, b_2 \in \Z$，如果 $a_1 \equiv b_1 \pmod m$ 且 $a_2 \equiv b_2 \pmod m$，那么根据 $a_1 a_2 \equiv b_1 b_2 \pmod m$。
**【剩余类的定义】**定义任意 $a \in \Z$ 对模数 $m \in \Z^+$ 的剩余类 (residue class) 为：
$$ [a]_m := \{ a + km \mid k \in \Z \} $$
【△剩余类就是同余导出的等价类】
证明
- 剩余类就是同余导出的等价类：根据定义只需证 $\forall m \in \Z^+$，$\forall a \in \Z$，$\{ a + km \mid k \in \Z \} = \{ z \mid z \in \Z \wedge a \equiv z \pmod m \}$。
- $\Rightarrow$：$\forall z \in \{ a + km \mid k \in \Z \}$，存在 $k \in \Z$ 使得 $z = a + km$，显然 $z \in \Z$ 且 $a \equiv z \pmod m$。
- $\Leftarrow$：$\forall z \in \{ z \mid z \in \Z \wedge a \equiv z \pmod m \}$，根据同余的对称性和同余的充要条件得到 $m \mid (z - a)$ 即存在 $k \in \Z$ 使得 $z - a = km$ 即 $z = a + km$。
【△所有剩余类所构成的集合就是同余导出的商集】
$$ \begin{align*}
\Z / {\equiv_m} &= \{ [a]_m \mid a \in \Z \} \\
&= \{ [a]_m \mid a \in \{ 0, 1, 2, \cdots, m-1 \} \} \\
\end{align*} $$
证明
- 剩余类构成的集合就是同余导出的商集：
- 第一个等号因为商集定义 $\Z / {\equiv_m} = \{ [a]_{\equiv_m} \mid a \in \Z \}$ 和 $\forall a$ 都有 $[a]m = [a]{\equiv_m}$ 立得成立。
- 第二个等号：
- $\Leftarrow$：显然成立。
- $\Rightarrow$：$\forall A \in \{ [a]_m \mid a \in \Z \}$，存在 $a \in \Z$ 使得 $A = [a]_m$。根据等价类定义我们知道 $\forall b \in \Z$，$[a]_m = [b]_m \Leftrightarrow a \equiv b \pmod m$。那么我们作整数除法 $a = km + r$（$k \in \Z$，$r \in \Z \cap [0, m)$）有 $a \equiv r \pmod m$ 因而 $[a]_m = [r]_m \in \{ [a]_m \mid a \in \{ 0, 1, 2, \cdots, m-1 \}$。
- 等价类 $[a]_{\equiv_m} = m\Z + a$（陪集）：
- 根据对 $m\Z$ 的认识（详见「子环」章节），有 $m\Z = \{ k m \mid k \in \Z \}$。
- 因而 $m\Z + a = \{ a + k m \mid k \in \Z \}$。根据 $[a]m$ 定义知道 $[a]{\equiv_m} = [a]_m = m\Z + a$。
- 商集 $\Z / {\equiv_m} = \Z / m\Z$（商环）：
- 根据对 $\Z / m\Z$ 的认识（详见「子环」章节），有 $\Z / m\Z = \{ m\Z+a \mid a \in \Z \}$ 。
- 因而 $\Z / m\Z = \{ m\Z+a \mid a \in \Z \} = \{ [a]_m \mid a \in \Z \} = \Z / {\equiv_m}$。
**【△剩余类环是同余导出的商代数】**只要定义商代数中剩余类之间的二元运算 $\oplus$ 和 $\otimes$（运算定义为：用代表元素运算所得元素的等价类，良定义性从同余关系定义导出），就能构成 $\lang \Z, +, \times \rang$ 关于同余关系 $\equiv_m$ 的商代数 $\lang \Z / {\equiv}_m, \oplus, \otimes \rang$。商代数仍然是一个代数系统。而且，$\lang \Z / {\equiv}_m, \oplus, \otimes \rang = \lang \Z / m\Z, \bar+, \bar \times \rang$（这里 $\bar+$、$\bar \times$ 是商环 $\Z / m\Z$ 中衍生的运算）。进一步地，这个商代数是一个交换的幺环。
说明
- 想要证明两个代数系统相同，只需说明：二元关系同余 $\equiv_m$ 就是商环 $\Z / m\Z$ 中涉及的「陪集相等」等价关系 $F_\rightarrow$ （定义为 $\forall a, b \in \Z$，$a F_\rightarrow b :\Leftrightarrow m\Z + a = m\Z + b$）。只需证 $m\Z + a = m\Z + b \Leftrightarrow a \equiv b \pmod m$。这很容易证明，因为根据 $[a]{\equiv_m} = m\Z + a$ 和 $[b]{\equiv_m} = m\Z + b$，马上得到：
$$ m\Z + a = m\Z + b \iff [a]{\equiv_m} = [b]{\equiv_m} \iff a \equiv b \pmod m $$
- 我们早就知道商环 $\Z / k\Z$ 是一个交换的幺环。详见「商环的实例」，乘法 ($\bar \times$) 有交换律且单位元为 $k\Z + 1$）。
【常用运算结论】$\forall m \in \Z^+$，$\forall a, b, c, d \in \Z$：
还可以复合成如「$[a]_m \oplus [b]_m = [c]_m \otimes [d]_m \iff \exists k \in \Z, \, a + b - cd = km$」等形态。
证：
回顾重要结论：
等价类和陪集的关系 $[a]_m = m\Z + a$。
对于环 $\Z$ 及其理想 $m\Z$，记 $\Z/m\Z$ 中的加法和乘法为 ${\bar +}$ 和 ${\bar \cdot}$ ，有：
- $\forall a, b \in \Z$，$(m\Z + a) \, {\bar +} \, (m\Z + b) = m\Z + (a + b)$；
- $\forall a, b \in \Z$，$(m\Z + a) \, {\bar \cdot} \, (m\Z + b) = m\Z + (a \cdot b)$。
陪集相同的充要条件
- 上面证明了 $m\Z + a = m\Z + b \iff a \equiv b \pmod m$；
- 同余充要条件 $a \equiv b \pmod m \iff \exists k \in \Z , \, a - b = km$。
得到：
$$ m\Z + a = m\Z + b \iff \exists k \in \Z , \, a - b = km $$
根据上面的结论，马上就能将剩余类的等式转为陪集等式再运算，然后通过陪集相同的充要条件等价到算式中。
**【△整数环到剩余类环的环同态】**记录 $\pi:\Z \to \Z / {\equiv_m}$，$\pi (a) = [a]_m = m \Z + a$，根据「同余关系能导出同态映射」，$\pi$ 是 $\Z \to \Z / {\equiv_m}$（后者是商代数）的同态；又 $\Z / {\equiv_m} = \Z / m\Z$，因而 $\pi$ 也是 $\Z \to \Z / m\Z$（两个环之间）的环同态。
**【△剩余类环同构于 $Z_m$】**对于 $m \in \Z^+$，剩余类环 $\lang \Z / m\Z, \bar+, \bar \times \rang \cong Z_m := \lang \Z_m, \oplus_m, \otimes_m \rang$（$\oplus_m$ /$\otimes_m$是先运算 $+$/$\times$ 后作整数除法求余）。
证
- 定义映射 $\phi: \Z_m \to \Z / m\Z$，$\phi(a) = m\Z + a$。显然 $\phi = \pi \mid \Z_m$（$\Z_m \subseteq \Z$），容易检验良定义性 $m\Z + a \in \Z / m\Z$。
- 证明双射性：
之前已经说明过 $\Z / {\equiv_m} = \{ [a]_m \mid a \in \{ 0, 1, 2, \cdots, m-1 \} \}$，很容易得到：
$$ \Z / m\Z = \{ m \Z + a \mid a \in \Z_m \} = \{ \phi(a) \mid a \in \Z_m \} $$
满射性：$\forall A \in \Z / m\Z$，$\exists a \in \Z_m$ 使得 $\phi(a) = A$。
单射性：反证法，设 $\exists a, b \in \Z_m$，$\phi (a) = \phi(b)$ 且 $a \neq b$。$\phi (a) = \phi(b)$ 导出 $a \equiv b \pmod m$ 导出 $m \mid (a-b)$ 导出 $a = b$ 或者 $|a - b| \ge m$。由于 $a, b \in \Z_m$，只有 $a = b$ 能成立，发生矛盾。
- 证明 $\phi$ 保持运算（需要利用限制前的 $\pi$）：
- 加法：$\forall a, b \in \Z_m$：
- 因为 $(m\Z + a) \, {\bar +} \, (m\Z + b) = m\Z + (a + b)$ 导出 $\pi(a) \, {\bar +} \, \pi(b) = \pi(a + b)$。
- 又 $a + b \equiv a \oplus_m b \pmod m$，因而 $\pi(a + b) = \pi(a \oplus_m b)$。
- 从而 $\pi(a) \, {\bar +} \, \pi(b) = \pi(a \oplus_m b)$，由于 $a, b, a \oplus_m b \in \Z_m$ 限制后版本即 $\phi(a) \, {\bar +} \, \phi(b) = \phi(a \oplus_m b)$。
- 乘法：$\forall a, b \in \Z_m$：
- 因为 $(m\Z + a) \, {\bar \times} \, (m\Z + b) = m\Z + (a \times b)$ 导出 $\pi(a) \, {\bar \times} \, \pi(b) = \pi(a \times b)$。
- 又 $a \times b \equiv a \otimes_m b \pmod m$，因而 $\pi(a \times b) = \pi(a \otimes_m b)$。
- 从而 $\pi(a) \, {\bar \times} \, \pi(b) = \pi(a \otimes_m b)$。由于 $a, b, a \otimes_m b \in \Z_m$ 限制后版本即 $\phi(a) \, {\bar \times} \, \phi(b) = \phi(a \otimes_m b)$。