同余基础

在整除理论中，我们习惯于问"$a$ 能不能被 $m$ 整除"——这是一个非此即彼的问题，答案只有"是"与"否"两种。但整数与整数之间的关系远比这丰富，还有一种更细腻的视角值得挖掘：当 $a$ 不能被 $m$ 整除时，它被 $m$ 除后余下多少？当两个数被同一个数 $m$ 除后，恰好留下相同的余数，它们之间藏着什么共同结构？这个问题，引出了数论中最具威力的工具之一：同余（Congruence）。

十九世纪初，数学家高斯（Carl Friedrich Gauss）在他的名著《算术研究》（Disquisitiones Arithmeticae，1801年）中，把"余数相同"这个朴素直觉提炼成了一套精密的代数语言，并由此发展出影响深远的同余理论。今天，同余是初等数论的核心语言，是竞赛数学的基本技巧，也是现代密码学（RSA 算法）的数学根基。理解了同余，你就拥有了一把能在"模的世界"里把大数计算化为小数计算的利器。

从时钟说起：同余的直觉

为什么"下午 $3$ 点"和"$15$ 点"是同一个时刻？因为 $15 = 12 + 3$，也就是说 $15$ 除以 $12$ 余 $3$，而 $3$ 除以 $12$ 也余 $3$。在 $12$ 小时制的时钟里，$3$ 和 $15$ 在"名义上"完全等价——时钟转完一圈回到原位，时间又从头数起。$13$ 等同于 $1$，$25$ 等同于 $1$，$15$ 等同于 $3$，这种"绕圈转"的等价关系，正是同余的直觉原型。

时钟的例子揭示了同余的本质：不是问两数是否相等，而是问它们除以某个固定数 $m$（在时钟里是 $12$）之后，余数是否相同。一旦余数相同，两个数在"模 $m$ 的视角"下就完全等价，可以相互替换。高斯把这种等价关系符号化，使它成为可以精确推导的数学工具，而不再只是经验性的观察。

同余的定义

"$m \mid (a - b)$"与"$a$ 和 $b$ 除以 $m$ 余数相同"是完全等价的两种表述，可以视情况灵活选用。后者更直观，前者在证明中更方便操作——特别是当 $a$ 或 $b$ 是负数时，从"差能被 整除"出发，不必纠结负数的余数定义，逻辑更清晰。

几个关键例子帮助建立感觉。$17 \equiv 5 \pmod{6}$，因为 $17 - 5 = 12 = 6 \times 2$；$-1\equiv 11(\mathrm{m}$，因为 ；，因为 ；时钟的例子 ，因为 。这四个例子覆盖了正数、负数、整除等特殊情形，值得逐一体会。

若 $a$ 除以 $m$ 的带余除法余数为 $r$（满足 $0 \leq r < m$），则 $a \equiv r \pmod{m}$，这个 叫做 关于模 的。每个整数关于给定的模都有唯一的最小非负余数，它在 中取值，是这个整数在"模 世界"里的"身份编号"。

同余是等价关系

认识了定义，下一步是弄清楚它满足什么性质。同余关系满足三条基本性质，合称等价关系（equivalence relation），这为后续所有推导奠定了逻辑基础。

自反性要求任何数与自己同余：$a \equiv a \pmod{m}$，因为 $a - a = 0$，而任何正整数都整除 $0$。对称性保证方向可以互换：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}$，则 ——这是因为 意味着 对某整数 成立，于是 ，故 。保证关系可以沿链传递：若 且 ，设 ，，则 ，故 。

这三条性质的意义远不只是技术性验证，它们共同揭示了一个结构性事实：同余关系把全体整数划分成若干个彼此不相交的子集——同一子集内的数两两同余，不同子集之间的数互不同余。这些子集就是剩余类（residue classes），整数世界由此被切割成了井然有序的"朋友圈"，每个圈子里的成员在"模 $m$ 的眼睛"里看起来完全相同。

同余的运算性质

同余最强大的地方，是它与加减乘运算完美兼容，可以在"模的世界"里自由做算术，而不必总是携带大数。

加法性质的证明最为典型，其余两条都是类似或应用加法的推导。设 $a - b = mk_1$，$c - d = mk_2$，则 ，故 ，加法性质得证。乘法性质可以写成 ，故 。

这些规则在实践中意味着：在求模 $m$ 下的结果时，随时可以将任何数替换为与它同余（通常更小）的数，而不影响整个算式关于模 $m$ 的余数。这正是同余化简大数计算的核心操作。

模运算在算法上有一套等价的描述：$(a + b) \bmod m = [(a \bmod m) + (b \bmod m)] \bmod m$，乘法类似。这意味着在任何计算过程的任意一步，都可以对中间结果取模，而不影响最终的余数——这是编程中处理大数模运算的基本技巧，在密码学算法实现中无处不在。以 为例：因为 ，故 ；进而 ；乘法规则给出 ，全程无需处理 这个大数。

剩余类与完全剩余系

同余将整数划分成若干"朋友圈"，每个圈子就是一个剩余类。精确地说，对正整数 $m$ 和整数 $r$，所有与 $r$ 关于模 $m$ 同余的整数构成的集合 $[r]_m = \{\ldots, r-2m, r-m, r, r+m, r+2m, \ldots\} = r + m\mathbb{Z}$，叫做。

对于模 $m$，恰好有 $m$ 个不同的剩余类：$[0]_m, [1]_m, \ldots, [m-1]_m$。它们两两不相交，合在一起穷尽全体整数。以 为例，全体整数被切成四份： 包含所有 的倍数（）， 包含除以 余 的所有整数（）， 和 类似。每个类都无限延伸，但类内的数在模 意义下完全等价。

从每个剩余类中各取一个代表元，共 $m$ 个数，构成模 $m$ 的一个完全剩余系（complete residue system）。最常用的是最小非负完全剩余系 $\{0, 1, 2, \ldots, m-1\}$，但选法不唯一——最小正完全剩余系 $\{1, 2, \ldots, m\}$、 、乃至随意从每个类中挑一个代表，都是合法的完全剩余系，只要每个剩余类恰好被代表一次。

线性同余方程

同余语言自然引出了一类重要方程：线性同余方程 $ax \equiv b \pmod{m}$，其中 $a, b, m$ 已知，求未知整数 $x$。

线性同余方程有解的充要条件是 $\gcd(a, m) \mid b$，即 $a$ 与 $m$ 的最大公因数整除 $b$。若此条件不满足，方程根本无解——例如 $4x \equiv 3 \pmod{6}$，，而 ，故无解。若条件满足，设 ，则在模 意义下恰好有 个不同的解，这 个解关于模 两两不同余，形成等差间隔为 的完整解系。

最常用的情形是 $\gcd(a, m) = 1$，此时方程恰有唯一解（模 $m$）。求解的标准路径是找 $a$ 关于模 $m$ 的乘法逆元，即满足 $ax_0 \equiv 1 \pmod{m}$ 的整数 （记作 ）；找到之后，原方程的解就是 。乘法逆元的存在性正是由 保证的——裴蜀定理告诉我们此时存在整数 使得 ，即 ，这也说明了为什么互质条件不可少：若 ，则 的最小正值是 ，不可能等于 ，逆元不存在。

例题精讲

例题一：同余关系的判断与推导

题目：判断以下是否成立，并说明理由：（1）$37 \equiv 13 \pmod{8}$；（2）$-15 \equiv 9 \pmod{6}$；（3）$100\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}$。

例题二：利用周期性计算大数幂的余数

题目：计算 $3^{100} \bmod 7$。

例题三：同余证明整除性

题目：证明对所有非负整数 $n$，$7 \mid (3^{2n+1} + 2^{n+2})$。

例题四：解线性同余方程

题目：解方程 $5x \equiv 3 \pmod{14}$，写出全部解。

例题五：数字整除性的同余判断

题目：不做大数除法，判断 $123456789$ 能否被 $9$ 整除。

例题六：线性同余方程无解的情形

题目：证明方程 $4x \equiv 3 \pmod{6}$ 无解，并说明原因。

同余的深远应用

同余理论的应用远不止于初等计算技巧，它是现代密码学的数学根基。RSA 公钥密码系统——今天互联网安全传输的主要保障——的核心就是模运算与同余。其加密和解密过程依赖欧拉定理 $a^{\varphi(n)} \equiv 1 \pmod{n}$（$\varphi$ 是欧拉函数），而整个系统的安全性来自一个数论事实：给定两个大素数 $p$ 和 $q$，计算它们的乘积 只需瞬间，但反过来从 还原出 和 （即大数分解），在 有数百位时，以现有计算机需要数亿年。今天学习的同余基础，正是通往这个宏大理论大厦的入口。

练习

练习一：求 $7^{200} \bmod 11$（提示：先计算 $7^1, 7^2, \ldots$ 关于模 $11$ 的余数，找出周期）。

练习二：解方程 $7x \equiv 2 \pmod{10}$，写出模 $10$ 意义下的唯一解，并找出 $-20$ 到 $20$ 范围内的所有解。

练习三：证明对所有正整数 $n$，$13 \mid (3^{2n} - 9^n + 4^{n+1} - 4)$（提示：先求 ，， 分别等于多少，然后合并）。

要点收束

同余用 $a \equiv b \pmod{m}$ 这一简洁符号揭示了整数在"模 $m$ 视角"下的内在结构。它的定义是 $m \mid (a - b)$，等价于 $a$ 和 除以 的余数相同。同余是等价关系（自反、对称、传递），它把全体整数划分为 个剩余类，每个类内的数在加减乘运算中可以自由互换。这种运算兼容性是同余最强大的地方：处理大数幂次、整除性证明、线性方程的求解，都因此变得可以"化大为小"。除法是唯一需要警惕的操作——只有当除数与模互质时，才可以同步地约分，否则模需要随之缩小。剩余类和完全剩余系将同余的组织结构系统化，为欧拉定理、中国剩余定理等更深层的结论铺好了地基。线性同余方程 有解的充要条件是 ，互质情形下唯一解通过乘法逆元（结合裴蜀定理）求得，整个理论在密码学 RSA 算法中得到了最壮观的应用。

$a \equiv b \pmod{m}$

其中 $m$ 称为这个同余关系的模（modulus）。若 $m \nmid (a - b)$，则称 $a$ 与 $b$ 关于模 $m$ 不同余，记作 $a \not\equiv b \pmod{m}$。

周期为 $10$。$200 = 10 \times 20$，故 $7^{200} = (7^{10})^{20} \equiv 1^{20} = 1 \pmod{11}$。

实际上这里 $7^{10} \equiv 1 \pmod{11}$ 是费马小定理的一个特例：对素数 $p$ 和不被 $p$ 整除的整数 $a$，有 $a^{p-1} \equiv 1 \pmod p$。此处 $p = 11$，$a = 7$，$p - 1 = 10$，恰好对应。费马小定理是下一篇将要深入讲述的内容。

$x \equiv 3 \times 2 = 6 \pmod{10}$。

验证：$7 \times 6 = 42 = 4 \times 10 + 2$，故 $7 \times 6 \equiv 2 \pmod{10}$，正确。

在 $-20$ 到 $20$ 内，满足 $x \equiv 6 \pmod{10}$ 的整数有：$-14, -4, 6, 16$。

对剩余部分 $4^{n+1} - 4 = 4(4^n - 1)$：需证 $13 \mid 4(4^n - 1)$，因 $\gcd(4, 13) = 1$，等价于证 $13 \mid (4^n - 1)$，即 $4^n \equiv 1 \pmod{13}$。计算 $4^1 \equiv 4$，$4^2 \equiv 16 \equiv 3$，$4^3 \equiv 12 \equiv -1$，$4^6 \equiv (-1)^2 = 1 \pmod{13}$，周期为 $6$。但要对所有正整数 $n$ 成立，需要 $6 \mid n$，这对一般的 $n$ 不成立。

重新核查题目：$3^{2n} - 9^n = 9^n - 9^n = 0$，第一部分确实为 $0$；第二部分 $4^{n+1} - 4$ 对 $n = 1$：$4^2 - 4 = 12$，$13 \nmid 12$。

注意题目可能有笔误。若题目为 $13 \mid (3^{2n} - 9^n)$，则因 $3^{2n} = 9^n$ 恒成立，差为 $0$，被任何数整除，结论平凡成立。读者在遇到类似题目时，先验证小情形（$n=1,2$）可以快速发现潜在问题。