模 n 同余类简介

整数之间的除法未必能够整除。小学数学中，在引入有理数前我们使用余数来描述无法除尽的部分，而完整研究余数相关性质的理论——数论（number theory）——却在大学数学中才引入，这是因为其具有浓厚的代数学风格．虽然我们的主题是抽象代数，但作为其中最常用的实例，我们非常有必要了解余数相关的概念：模 n 同余类．

整除与最大公因数

定义 1 设 $a,b\in \mathbb{Z}$ 且 $b\ne 0$，若存在 $k\in \mathbb{Z}$ 使得 $a=bk$，则称 $b$ 整除（divide）$a$，或称 $b$ 为 $a$ 的因数（divisor，factor），记作 $b\mid a$．此时我们也称 $a$ 是 $b$ 的倍数（multiple）．

关于整除有若干非常显然的性质．

命题 1 对任意 $a,b,c,s,t\in \mathbb{Z}$ 且 $b\ne 0$：

• $b\mid 0$；
• 若 $b\mid a$，则 $b\mid sa$（特别地 $b\mid -a$）；
• 若 $b\mid a$ 且 $b\mid c$，则 $b\mid (sa+tc)$；
• 设 $a\ne 0$．若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$．

显然对任意 $b\in \mathbb{Z}\setminus \{0\}$ 都有 $b\mid 0$．

定义 2 设 $a,b,d\in \mathbb{Z}$ 且 $d\ne 0$，若 $d\mid a$ 且 $d\mid b$，则称 $d$ 是 $a$ 与 $b$ 的一个公因数（common divisor）．$a$ 与 $b$ 的公因数中的最大值称为其最大公因数（greatest common divisor），记作 $(a,b)$ 或 $\gcd (a,b)$．

最大公因数也有若干显然的性质．

命题 2 对任意 $a,b\in \mathbb{Z}$ 都有

• $\gcd (a,b)=\gcd (b,a)$；
• $\gcd (a,b)=\gcd (|a|,|b|)$；
• $\gcd (a,0)=|a|$；
• $\gcd (a,1)=1$．

与公因数相对，我们有公倍数，不过其应用场景相对较少．

定义 3 设 $a,b,m\in \mathbb{Z}$ 且 $a,b\ne 0$．若 $a\mid m$ 且 $b\mid m$，则称 $m$ 是 $a$ 与 $b$ 的一个公倍数（common multiple）．$a$ 与 $b$ 的公倍数中的最小值称为其最小公倍数（least common multiple），记作 $[a,b]$ 或 $\mathrm{lcm}(a,b)$．

定义 4 设 $p\in {\mathbb{Z}}^{+}$ 且 $p\ne 1$．若 $p$ 有且只有因数 $1$ 与 $p$ 本身，则称 $p$ 为素数（prime number）．

直观上，素数就是无法进一步有效分解出更小因数的数．

定义 5 设 $a,b\in \mathbb{Z}$，若 $(a,b)=1$，则称 $a$ 与 $b$ 互素（relatively prime）．

直观上，互素的数之间不存在（$1$ 以外的）公因数．

我们不加证明的给出算术基本定理（正整数唯一分解定理），它是处理整除关系与分析最大公因数性质的有力工具．读者很可能早已熟悉这个结论．

定理 3 对任意大于 $1$ 的正整数 $a$，存在有限个素数 $p_1,p_2,\dots ,p_n$ 使得

$$a=p_1{p}_2\cdots p_n.$$

若这些素数是有序排列的，即 $p_1\le p_2\le \cdots \le p_n$，则上述素因数分解形式是唯一的．

若将相同的素因数以幂的形式整合在一起，则定理可改写为：唯一存在有限个素数 $p_1<p_2<\cdots <p_{n^{\prime }}$ 以及正整数 ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{n^{\prime }}$ 使得

$$a=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_{n^{\prime }}^{{\alpha }_{n^{\prime }}}.$$

使用算术基本定理很容易证明以下性质：

命题 4 对任意正整数 $a$ 和 $b$ 都有

$$ab=\gcd (a,b)\cdot \mathrm{lcm}(a,b).$$

带余除法

当 $b\mid a$ 时，我们能在整数范围内计算除法 $a/b$．当 $b\nmid a$ 时，整数范围内的除法就会留下余数．

定理 5 设 $a,b\in \mathbb{Z}$ 且 $b\ne 0$，则唯一存在一对 $q,r\in \mathbb{Z}$ 满足

$$a=bq+r,0\le r<|b|.$$

我们称 $q$ 为 $a$ 除以 $b$ 的（不完全）商（quotient），称 $r$ 为 $a$ 除以 $b$（或 $a$ 模 $b$）的余数（remainder）．

在分析学中要严格地以没有循环论证的方式证明上述定理比较复杂，且依赖于整数的定义．我们不深究自然数与整数的定义，只给出一个能够被广泛接受的证明方法．

证明 我们首先证明 $q$ 与 $r$ 的存在性，然后证明其唯一性．

首先考虑 $b>0$ 的情形．在整个实数轴上可以取以下点列：

$$\dots ,-3b,-2b,-b,0,b,2b,3b,\dots ,$$

以它们为端点的区间 $[kb,(k+1)b)$ $(k\in \mathbb{Z})$ 构成 $\mathbb{R}$ 的划分．因此，对任意 $a\in \mathbb{Z}$，其必然位于某个区间中．

不妨设 $a\in [bq,b(q+1))$ $(q\in \mathbb{Z})$，令 $r:=a-bq\in \mathbb{Z}$，则 $r\in [0,b)$，因此我们有

$$a=bq+r,0\le r<b,$$

证毕．

再考虑 $b<0$ 的情形，此时 $-b=|b|>0$．沿用刚证明的结论，存在 $q^{\prime },r\in \mathbb{Z}$ 使得

$$a=|b|q^{\prime }+r,0\le r<|b|.$$

令 $q:=-q^{\prime }$ 得到 $a=bq+r$，证毕．

最后证明 $q$ 与 $r$ 的唯一性．假设同时存在 $q,q^{\prime },r,r^{\prime }\in \mathbb{Z}$ 使得

$$\begin{array}{rlr}a& =bq+r,& 0\le r<|b|,\\ a& =b{q}^{\prime }+r^{\prime },& 0\le r^{\prime }<|b|.\end{array}$$

二式相减得到

$$b(q-q^{\prime })=r^{\prime }-r.$$

取绝对值后得到 $|b|\cdot |q-q^{\prime }|=|r-r^{\prime }|$．根据 $r$ 与 $r^{\prime }$ 的取值范围，容易证明

$$-|b|<r-r^{\prime }<|b|,$$

即 $|r-r^{\prime }|<|b|$，因此 $|b|\cdot |q-q^{\prime }|<|b|$，即

$$|b|\cdot (|q-q^{\prime }|-1)<0.$$

这只可能有 $|q-q^{\prime }|-1<0$，即 $q=q^{\prime }$．进而 $r=a-bq=a-b{q}^{\prime }=r^{\prime }$，证毕．

按定义，带余除法的除数 $b$ 可以是任意非零整数，但我们主要关注其为正整数的情形．对任意 $a,b\in \mathbb{Z}$ 且 $b\ne 0$，显然 $b\mid a$ 当且仅当 $a$ 模 $b$（的余数）为 $0$．

考虑任意正整数 $n$，模 $n$ 所能得到的余数恰有 $n$ 个，即

$$0,1,2,\dots ,n-1.$$

全体模 $n$ 得到相同余数 $r$ 的整数均具有形式 $kn+r$ $(k\in \mathbb{Z})$．

模 n 同余类

定义 6 设 $n\in {\mathbb{Z}}^{+}$，$a,b\in \mathbb{Z}$，若 $a$ 和 $b$ 模 $n$ 的余数相同，则称它们是同余的（congruent），记作

$$a\equiv b(\mathrm{mod}n).$$

事实上在数论中我们一般采用同余的另一个等价定义，它更适合用于证明其他性质．

命题 6 设 $n\in {\mathbb{Z}}^{+}$，$a,b\in \mathbb{Z}$，则 $a\equiv b(\mathrm{mod}n)$ 当且仅当 $n\mid (b-a)$．

证明 （$⟹$）设 $a$ 和 $b$ 模 $n$ 具有相同余数，即存在 $q,q^{\prime },r\in \mathbb{Z}$ 满足

$$a=nq+r,b=n{q}^{\prime }+r.$$

于是 $b-a=n(q^{\prime }-q)$，故 $n\mid (b-a)$．

（$⟸$）设 $n\mid (b-a)$，即存在 $k\in \mathbb{Z}$ 使得 $b-a=kn$．设 $q,q^{\prime },r,r^{\prime }\in \mathbb{Z}$ 满足

$$\begin{array}{rlr}a& =nq+r,& 0\le r<n,\\ b& =n{q}^{\prime }+r^{\prime },& 0\le r^{\prime }<n,\end{array}$$

则

$$kn=b-a=n(q^{\prime }-q)+(r^{\prime }-r),$$

因此 $|r^{\prime }-r|=n\cdot |k-q^{\prime }+q|$．由于 $|r^{\prime }-r|<n$，这只可能有 $r^{\prime }=r$．

记号 $a\equiv b(\mathrm{mod}n)$ 中，$\equiv$ 应当理解为类似“$=$”的等价关系符号，而后面的括号用于补充说明除数．

命题 7 同余关系是等价关系，即对任意 $n\in {\mathbb{Z}}^{+}$ 和 $a,b,c\in \mathbb{Z}$ 都有：

• 自反性：$a\equiv a(\mathrm{mod}n)$；
• 对称性：若 $a\equiv b(\mathrm{mod}n)$，则 $b\equiv a(\mathrm{mod}n)$；
• 传递性：若 $a\equiv b(\mathrm{mod}n)$ 且 $b\equiv c(\mathrm{mod}n)$，则 $a\equiv c(\mathrm{mod}n)$．

证明 直接由整除的性质得到．

等价关系可以确定等价类并划分全集．对任意 $a\in \mathbb{Z}$，其在模 $n$ 的同余关系下的等价类记作 $[a{]}_n$，称为 $a$ 对应的模 $\mathbf{n}$ 同余类（congruence class modulo $n$）．显然

$$[a{]}_n=\{a+kn|k\in \mathbb{Z}\}.$$

由于不同的余数只有 $n$ 个，全体模 $n$ 同余类也只有 $n$ 个，它们构成的集合记作 $\mathbb{Z}/n\mathbb{Z}$，通常称为 $\mathbf{n}$ 阶循环群（cyclic group of order $n$）或 模 $\mathbf{n}$ 加法群（additive group modulo $n$）．这些记号和名称的来源会在学习群论后明晰．显然

$$\mathbb{Z}/n\mathbb{Z}=\{[0{]}_n,[1{]}_n,\dots ,[n-1{]}_n\}.$$

例如，当 $n=2$ 时，

$$\begin{array}{rl}[0{]}_2& =\{\dots ,-4,-2,0,2,4,\dots \},\\ [1{]}_2& =\{\dots ,-3,-1,1,3,5,\dots \}\end{array}$$

分别为偶数和奇数构成的集合，它们不相交但遍历所有整数．

同余类可与整数一样定义加法和乘法运算．设 $n$ 为正整数，对任意整数 $a$ 和 $b$，定义

$$\begin{array}{rl}[a{]}_n+[b{]}_n& :=[a+b{]}_n,\\ [a{]}_n\cdot [b{]}_n& :=[ab{]}_n.\end{array}$$

然而我们还需要证明这样的运算是良定义的．例如，设 $a\equiv a^{\prime }(\mathrm{mod}n)$ 且 $b\equiv b^{\prime }(\mathrm{mod}b)$，即 $[a{]}_n=[a^{\prime }{]}_n$ 且 $[b{]}_n=[b^{\prime }{]}_n$，则应当有

$$[a^{\prime }+b^{\prime }{]}_n=[a^{\prime }{]}_n+[b^{\prime }{]}_n=[a{]}_n+[b{]}_n=[a+b{]}_n,$$

只有满足上述条件才能定义出模 $n$ 同余类上的加法运算．

引理 8 设 $n\in {\mathbb{Z}}^{+}$，$a,a^{\prime },b,b^{\prime }\in \mathbb{Z}$．若 $a\equiv a^{\prime }(\mathrm{mod}n)$ 且 $b\equiv b^{\prime }(\mathrm{mod}n)$，则

$$\begin{array}{rl}a+b& \equiv a^{\prime }+b^{\prime }(\mathrm{mod}n),\\ ab& \equiv a^{\prime }{b}^{\prime }(\mathrm{mod}n).\end{array}$$

证明 根据同余的性质，存在 $k,\ell \in \mathbb{Z}$ 使得

$$a^{\prime }-a=kn,b^{\prime }-b=\ell n.$$

对于加法情形，

$$(a^{\prime }+b^{\prime })-(a+b)=(a^{\prime }-a)+(b^{\prime }-b)=(k+\ell )n,$$

因此 $n\mid [(a^{\prime }+b^{\prime })-(a+b)]$，亦即 $a+b\equiv a^{\prime }+b^{\prime }(\mathrm{mod}n)$．

对于乘法情形，

$$a^{\prime }{b}^{\prime }-ab=(a+kn)(b+\ell n)-ab=(a\ell +bk+k\ell n)\cdot n,$$

因此 $n\mid (a^{\prime }{b}^{\prime }-ab)$，亦即 $ab\equiv a^{\prime }{b}^{\prime }(\mathrm{mod}n)$．

这实际上也说明同余关系几乎能像等号一样处理加法和乘法运算．

考虑 $[5{]}_6$，我们考虑其倍数（也就是通过不断加 $[5{]}_6$ 得到其他同余类）能够得到

$$\begin{array}{rlrl}[5{]}_6,& & [10{]}_6& =[4{]}_6,\\ [15{]}_6& =[3{]}_6,& [20{]}_6& =[2{]}_6,\\ [25{]}_6& =[1{]}_6,& [30{]}_6& =[0{]}_6.\end{array}$$

我们发现这正好遍历了 $\mathbb{Z}/6\mathbb{Z}$．换言之，只使用 $[5{]}_6$ 与加法我们就能得到任意的模 $6$ 剩余类，我们称 $[5{]}_6$ 为 $\mathbb{Z}/6\mathbb{Z}$ 的生成元（generator）．一般地，对于 $[a{]}_n$，如果所有的模 $n$ 剩余类都能写成形式 $[ka{]}_n$ $(k\in \mathbb{Z})$，则称 $[a{]}_n$ 生成（genrate）$\mathbb{Z}/n\mathbb{Z}$．显然 $[1{]}_n$ 一定是生成元．在后续学习群论的过程中，我们会得以下结论：

命题 9 设 $n\in {\mathbb{Z}}^{+}$，$[a{]}_n\in \mathbb{Z}/n\mathbb{Z}$，则 $[a{]}_n$ 生成 $\mathbb{Z}/n\mathbb{Z}$ 当且仅当 $\gcd (a,n)=1$．

同余类的乘法未必可逆，例如

$$[2{]}_8\cdot [3{]}_8=[6{]}_8=[2{]}_8\cdot [7{]}_8,$$

这就无法定义 $[6{]}_8$ 除以 $[2{]}_8$．在实数中，除以一个数等价于乘以其倒数，因此我们在一般情形下都用乘法描述除法．

设 $a,b\in \mathbb{Z}/n\mathbb{Z}$，若 $ab\equiv 1(\mathrm{mod}n)$，则称 $a$ 和 $b$ 互为（乘法）逆元（inverse），记 $b=a^{-1}$．

显然若 $[a{]}_n$ 是生成元，则它可生成 $[1{]}_n$，即存在 $[b{]}_n\in \mathbb{Z}/n\mathbb{Z}$ 使得 $[ab{]}_n=[1{]}_n$，从而 $[b{]}_n$ 是其逆元．反之，若 $[ab{]}_n=[1{]}_n$，则对任意 $[c{]}_n\in \mathbb{Z}/n\mathbb{Z}$ 都有

$$[c{]}_n=[ab{]}_n\cdot [c{]}_n=[a{]}_n\cdot [bc{]}_n,$$

因此 $[a{]}_n$ 是生成元．于是我们得到了以下结论：

命题 10 设 $n\in {\mathbb{Z}}^{+}$，$[a{]}_n\in \mathbb{Z}/n\mathbb{Z}$，则 $[a{]}_n$ 存在逆元当且仅当 $[a{]}_n$ 生成 $\mathbb{Z}/n\mathbb{Z}$，当且仅当 $\gcd (a,n)=1$．