同余与剩余类

1. 同余解决什么问题

有些问题不关心整数的绝对大小，只关心除以某个数后的余数。例如星期、钟表、循环数组和哈希桶都具有这种周期性。

同余（Congruence）把“余数相同”写成一个严格的数学关系。

---

2. 同余的定义

对整数 $a,b$ 和正整数 $n$，

$$a\equiv b\pmod n$$

表示

$$n\mid(a-b).$$

也就是说，$a-b$ 是 $n$ 的整数倍。它等价于 $a$ 与 $b$ 除以 $n$ 后余数相同。

例如：

$$17\equiv5\pmod{12},$$

因为

$$17-5=12,qquad 12\mid12.$$

---

3. 钟表类比及其边界

模 12 可以想象成一个只有 12 个位置的钟表：5、17 和 29 都落在同一个位置，因为

$$17\equiv5\pmod{12},$$ $$29\equiv5\pmod{12}.$$

这个类比有助于形成直觉，但严格定义始终是 $12\mid(a-b)$。同余并不表示两个整数在普通整数意义下相等。

---

4. 剩余类

把所有与 $a$ 模 $n$ 同余的整数放在一起，得到 $a$ 的剩余类：

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

模 $n$ 一共有 $n$ 个不同的剩余类，通常用代表元表示为

$$\mathbb Z_n=\{0,1,\dots,n-1\}.$$

例如

$$\mathbb Z_5=\{0,1,2,3,4\}.$$

这里的每个数字代表一个剩余类，而不只是单个整数。

---

5. 剩余类上的运算

加法定义为

$$[a]+[b]=[a+b],$$

乘法定义为

$$[a][b]=[ab].$$

例如在模 5 下：

$$3+4=7\equiv2\pmod5,$$

所以 $[3]+[4]=[2]$。

乘法同样成立：

$$3 * 4=12\equiv2\pmod5.$$

这些定义不会依赖所选代表元。例如把 3 换成同一剩余类中的 8，仍有

$$8+4=12\equiv2\pmod5.$$

---

6. 等号与同余号

以下两句话含义不同：

$$17=5$$

在整数中为假；而

$$17\equiv5\pmod{12}$$

为真。

在已经明确工作于 $\mathbb Z_5$ 的语境中，有时会简写“$3+4=2$”。更完整的写法是

$$3+4\equiv2\pmod5.$$

初学阶段保留模数可以减少误解。

---

7. 负数如何取模

例如在模 5 下：

$$-1\equiv4\pmod5,$$

因为

$$-1-4=-5,qquad 5\mid(-5).$$

编程语言对负数取余的具体返回值可能不同，因此需要区分数学上的剩余类与某个语言的 % 运算符规则。

---

8. 自测

1. $29\equiv5\pmod{12}$ 为什么成立？
2. $[2]_5$ 中包含哪些形式的整数？
3. 在模 7 下，$5+6$ 属于哪个剩余类？
4. 为什么同余不等于普通相等？

参考答案

1. 因为 $29-5=24$，且 $12\mid24$。
2. 所有形如 $2+5k$ 的整数，其中 $k\in\mathbb Z$。
3. $5+6=11\equiv4\pmod7$。
4. 同余只要求两数之差是模数的整数倍。

上一篇：欧几里得算法与 Bézout 等式。
下一篇：模逆元：模运算中的除法。