本节对应原书 PDF 第 272–274 页（印刷 p257–p259）。定义、性质、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

定义 11.5 设 m 是正整数，a 和 b 是整数。如果 m \mid a-b，则称 a 模 m 同余于 b，或 a 与 b 模 m 同余，记作 a \equiv b(\bmod\ m)。如果 a 与 b 模 m 不同余，则记作 a \not\equiv b(\bmod\ m)。

不难验证，下述两条都是 a 与 b 模 m 同余的充分必要条件：

（1）a 与 b 除以 m 的余数相同，即 a\ \bmod\ m = b\ \bmod\ m。

（2）a = b+km，其中 k 是整数。

例如，15 \equiv 3(\bmod\ 4)，16 \equiv 0(\bmod\ 4)，14 \equiv -2(\bmod\ 4)，15 \not\equiv 16(\bmod\ 4)。

解读：定义说的是「a-b 被 m 整除」，而两条等价条件说的是「余数相同」和「相差整数个 m」。做题时三条可以随手换用：要证同余就用整除，要算具体值就用余数，要做代数变形就用 a = b+km。

同余具有下述性质：

性质 11.3.1 同余关系是等价关系，即同余关系具有

（i）自反性。a \equiv a(\bmod\ m)。

（ii）传递性。a \equiv b(\bmod\ m)，b \equiv c(\bmod\ m) \Rightarrow a \equiv c(\bmod\ m)。

（iii）对称性。a \equiv b(\bmod\ m) \Rightarrow b \equiv a(\bmod\ m)。

由传递性，常把 a_1 \equiv a_2(\bmod\ m)，a_2 \equiv a_3(\bmod\ m)，\cdots，a_{k-1} \equiv a_k(\bmod\ m) 缩写成 a_1 \equiv a_2 \equiv \cdots \equiv a_k(\bmod\ m)。

性质 11.3.2 模算术运算 若 a \equiv b(\bmod\ m)，c \equiv d(\bmod\ m)，则

a \pm c \equiv b \pm d(\bmod\ m),\quad ac \equiv bd(\bmod\ m),\quad a^k \equiv b^k(\bmod\ m)

其中 k 是非负整数。

解读：性质 11.3.2 是「同余式可以像等式一样做加减乘和乘方」的正式授权，也是后面所有模运算计算的依据。注意它只授权乘方，不授权取对数，也不授权用除法——除以一个数与模不互素的因子必须格外小心（见性质 11.3.5）。

性质 11.3.3 设 d \geqslant 1，d \mid m，则 a \equiv b(\bmod\ m) \Rightarrow a \equiv b(\bmod\ d)。

性质 11.3.4 设 d \geqslant 1，则 a \equiv b(\bmod\ m) \Leftrightarrow da \equiv db(\bmod\ dm)。

性质 11.3.5 设 c 与 m 互素，则 a \equiv b(\bmod\ m) \Leftrightarrow ca \equiv cb(\bmod\ m)。

解读：性质 11.3.5 里的「c 与 m 互素」不是装饰条件，去掉它就错。例如 2 \times 3 \equiv 2 \times 0(\bmod\ 6) 成立，但 3 \not\equiv 0(\bmod\ 6)。原因是要从 m \mid c(a-b) 推出 m \mid a-b，必须把 c 从整除式中「约掉」。

上述性质的证明留给读者（见习题 11.31～习题 11.33）。

整数 a 在模 m 同余关系下的等价类记作 [a]_m，称作 a 的模 m 等价类。在不会引起混淆的情况下，可略去下标 m，简记作 [a]。把整数集 \mathbf{Z} 在模 m 同余关系下的商集记作 \mathbf{Z}_m。根据性质 11.3.2，可以在 \mathbf{Z}_m 上定义加法和乘法如下：对任意的整数 a,b，

[a]+[b] = [a+b],\quad [a] \cdot [b] = [ab]

解读：这两个定义式之所以「合法」，是因为等号右边必须与代表元的取法无关：若 [a] = [a']、[b] = [b']，则由性质 11.3.2 有 [a+b] = [a'+b']、[ab] = [a'b']。也就是说，性质 11.3.2 的真正作用是保证 \mathbf{Z}_m 上的运算定义良好。

例 11.6 写出 \mathbf{Z}_5 的全部元素以及 \mathbf{Z}_5 上的加法表和乘法表。

解 \mathbf{Z}_5 = \{[0],[1],[2],[3],[4]\}，其中 [i] = \{5k+i \mid k \in \mathbf{Z}\}，i = 0,1,2,3,4。

加法表和乘法表分别如表 11.3 和表 11.4 所示。

表 11.3

+[0][1][2][3][4]
[0][0][1][2][3][4]
[1][1][2][3][4][0]
[2][2][3][4][0][1]
[3][3][4][0][1][2]
[4][4][0][1][2][3]

表 11.4

\cdot[0][1][2][3][4]
[0][0][0][0][0][0]
[1][0][1][2][3][4]
[2][0][2][4][1][3]
[3][0][3][1][4][2]
[4][0][4][3][2][1]

例 11.7 3^{455} 的个位数是多少？

解 设 3^{455} 的个位数为 x，则有 3^{455} \equiv x(\bmod\ 10)。由 3^4 \equiv 1(\bmod\ 10) 和性质 11.3.2，有

3^{455} = 3^{4 \times 113 + 3} \equiv 3^3 \equiv 7(\bmod\ 10)

故 3^{455} 的个位数是 7。

解读：求个位数就是求模 10 的余数，而 3^4 \equiv 1 使指数可以按 4 分组约掉。这类题的通用套路是先用性质 11.3.2 找「a^k \equiv 1 的短周期 k」，再把指数对 k 取余。

例 11.8 日期的星期数。

如何计算 y 年 m 月 d 日是星期几？为方便起见，用 0,1,\cdots,6 分别表示星期日，星期一，\cdots\cdots，星期六，称作星期数。整百年的年份，即 100C 的年份称作世纪年，C 称作该世纪年的世纪数。如 2000 年是世纪年，其世纪数为 20。

现在世界上通用的历法（阳历）是教皇格里高利十三世于 1582 年制定的，采用下述闰年规则：除世纪年外，每 4 年一个闰年，年数能被 4 整除的年为闰年。如 1840 年，1996 年和 2004 年是闰年。世纪数不能被 4 整除的世纪年不是闰年，如 1700 年，1800 年，1900 年和 2100 年不是闰年。而世纪数能被 4 整除的世纪年仍为闰年，如 1600 年，2000 年和 2400 年是闰年。平年一年 365 天，2 月 28 天。闰年一年 366 天，2 月 29 天。

由于 2 月有 28 天或 29 天，为计算方便，从 3 月 1 日开始算起，或者说，把 3 月看作第 1 月，12 月看作第 10 月，下一年的 1 月是第 11 月，2 月是第 12 月。于是，y 年 m 月 d 日现在变成 Y 年 M 月 d 日，其中 M = (m-3)\bmod 12+1，Y = y - \lfloor M/11 \rfloor。

由于 365 \equiv 1(\bmod\ 7)，3 月 1 日的星期数每过一个平年加 1，每过一个闰年还要多加一个 1（都是在模 7 下运算）。设 1600 年 3 月 1 日的星期数为 w_{1600}，y 年 3 月 1 日（Y 年 1 月 1 日）的星期数为 w_Y。设 y = Y = 100C+X，从 1600 年到 Y 年要经过 100C+X-1600 年，星期数应加

100C+X-1600 \equiv 2C+X+3(\bmod\ 7)

每 4 年一个闰年，有

\lfloor (100C+X-1600)/4 \rfloor = 25C+\lfloor X/4 \rfloor - 400

个闰年。考虑到世纪年，应从这个数中减去 C-16，再加 (C-16)/4 = \lceil C/4 \rceil - 4。因此，

\begin{aligned} w_Y &\equiv w_{1600} + (2C+X+3) + (25C+\lfloor X/4 \rfloor - 400) - (C-16) + (\lceil C/4 \rceil - 4) \\ &\equiv w_{1600} - 2C + X + \lfloor X/4 \rfloor + \lceil C/4 \rceil (\bmod\ 7) \end{aligned}

已知 2004 年 3 月 1 日是星期一，代入上式，

\begin{aligned} 1 &\equiv w_{1600} - 2 \times 20 + 4 + \lfloor 4/4 \rfloor + \lceil 20/4 \rceil \\ &\equiv w_{1600} + 5(\bmod\ 7) \end{aligned}

得 w_{1600} = 3，即 1600 年 3 月 1 日是星期三。于是，得到

w_Y \equiv 3 - 2C + X + \lfloor X/4 \rfloor + \lceil C/4 \rceil (\bmod\ 7) \tag{①}

接下来计算从当年 3 月 1 日到每个月 1 号的天数。除每个月加 30 天外，由于 3,5,7,8,10,12 月有 31 天，应另外加的天数 z 如表 11.5 所示。

表 11.5

M123456789101112
z011223445567

z 可表示成

\begin{aligned} z &= \begin{cases} \lfloor M/2 \rfloor & 1 \leqslant M \leqslant 6 \\ \lfloor (M+1)/2 \rfloor & 7 \leqslant M \leqslant 11 \\ \lfloor (M+1)/2 \rfloor + 1 & M = 12 \end{cases} \\ &= \lfloor (M+\lfloor M/7 \rfloor)/2 \rfloor + \lfloor M/12 \rfloor \end{aligned}

因此，M 月 d 日的星期数应在 w_Y 上加

\begin{aligned} &30(M-1) + \lfloor (M+\lfloor M/7 \rfloor)/2 \rfloor + \lfloor M/12 \rfloor + d - 1 \\ &\quad \equiv 2M + \lfloor (M+\lfloor M/7 \rfloor)/2 \rfloor + \lfloor M/12 \rfloor + d - 3(\bmod\ 7) \end{aligned} \tag{②}

最后，将 ①、② 两式合并，得到 y 年 m 月 d 日星期数的计算公式

w \equiv X+\lfloor X/4 \rfloor+\lfloor C/4 \rfloor-2C+2M+\lfloor (M+\lfloor M/7 \rfloor)/2 \rfloor+\lfloor M/12 \rfloor+d(\bmod\ 7)

其中 M = (m-3)\bmod 12 + 1，Y = y - \lfloor M/11 \rfloor = 100C+X。

例如，中华人民共和国成立日 1949 年 10 月 1 日，C = 19，X = 49，M = 8，d = 1，

\begin{aligned} w &\equiv 49+\lfloor 49/4 \rfloor+\lfloor 19/4 \rfloor-2 \times 19+2 \times 8+\lfloor (8+\lfloor 8/7 \rfloor)/2 \rfloor+\lfloor 8/12 \rfloor+1 \\ &\equiv 6(\bmod\ 7) \end{aligned}

是星期六。

中国人民抗日战争胜利日 1945 年 8 月 15 日，C = 19，X = 45，M = 6，d = 15，

\begin{aligned} w &\equiv 45+\lfloor 45/4 \rfloor+\lfloor 19/4 \rfloor-2 \times 19+2 \times 6+\lfloor (6+\lfloor 6/7 \rfloor)/2 \rfloor+\lfloor 6/12 \rfloor+15 \\ &\equiv 3(\bmod\ 7) \end{aligned}

是星期三。

解读：整个推导只反复用了一条 365 \equiv 1(\bmod\ 7)，把「过了多少天」翻译成「星期数加多少」。容易卡住的两处：一是把 3 月当作第 1 月（为了避开 2 月天数不定），二是世纪年闰年规则的修正项 -(C-16)+(\lceil C/4 \rceil - 4)——它是「先按每 4 年一个闰年全算，再把不是闰年的世纪年扣掉、把是闰年的世纪年补回来」。