同余

参考资料

• 同余 - 维基百科
• 费马小定理 - 维基百科
• 中国剩余定理 - 维基百科
• 同余 - OI Wiki

引入

同余（Congruence）是数论的「分类工具」——把所有整数按 除以 $m$ 的余数 归成 $m$ 类。它做的事情，就是把整数无穷无尽的乘法结构，搬到一个只有 $m$ 个元素的有限集 $\set{0,1,\dots,m-1}$ 上。

为什么要这么做？因为很多问题只关心余数，不关心整个数。比如「今天星期三，$100$ 天后星期几」，没人会真的去数 $100$ 天，而是看 $100\bmod 7=2$，往后推两天。同余就是把这种「只看余数」的直觉变成一套能严格运算的代数。它后来成了现代密码学（RSA、椭圆曲线）的核心语言。

同余的定义

整数 $a,b$，正整数 $m$，若 $m\mid(a-b)$，称 $a$ 同余于 $b$ 模 $m$，记为：

$$a\equiv b\pmod m$$

这里 $m$ 叫 模（Modulus）。等价的说法是：$a$ 与 $b$ 除以 $m$ 余数相同。两种定义可以随手互换——「差被 $m$ 整除」便于代数推导，「余数相同」便于直觉理解。

性质

等价关系

模 $m$ 同余满足 自反、对称、传递，因此它是 $\mathbb{Z}$ 上的一个 等价关系。等价关系会把整个集合切成互不相交的小块，这里切出的每一块就是下面要讲的「剩余类」。

运算保持

同余最有用的地方是它对加减乘 封闭。设 $a\equiv b,\ c\equiv d\pmod m$：

$$a\pm c\equiv b\pm d\pmod m,\quad ac\equiv bd\pmod m$$ $$a^k\equiv b^k\pmod m\quad(k\in\mathbb{N})$$

这意味着在任何加减乘（含乘方）的表达式里，都可以 随时把某个数换成它模 $m$ 的余数，结果模 $m$ 不变。算大数取模时，先把每个因子缩小再算，是最基本的提速手段。

例：求 $123\times 456\bmod 7$。先各自缩小：$123\equiv 4\pmod 7$（$123=7\times 17+4$），$456\equiv 1\pmod 7$（$456=7\times 65+1$），于是

$$123\times 456\equiv 4\times 1=4\pmod 7$$

不必真去算 $123\times 456=56088$ 再取模——先缩后算总是更轻。

例：判断 $2^{10}+1$ 能否被 $11$ 整除。$2^{10}=1024$，但直接看 $2^5=32\equiv 10\equiv-1\pmod{11}$，故 $2^{10}=(2^5)^2\equiv(-1)^2=1\pmod{11}$，于是 $2^{10}+1\equiv 2\pmod{11}\ne 0$，不能整除。把底数先压到 $\pm 1$ 再乘方，是手算幂模的常用捷径。

除法不自动成立

加减乘都没问题，唯独 除法（约去公因子）要小心：

$$ac\equiv bc\pmod m\nRightarrow a\equiv b\pmod m$$

比如 $2\times 3\equiv 2\times 0\pmod 6$，但 $3\not\equiv 0\pmod 6$。正确的约去法则是：

$$ac\equiv bc\pmod m\Rightarrow a\equiv b\pmod{\tfrac{m}{\gcd(c,m)}}$$

特别地，当 $\gcd(c,m)=1$ 时，模数不变，可以放心约去。这正是「互素」条件反复出现的原因。

剩余类与剩余系

剩余类

模 $m$ 把整数分成 $m$ 个 剩余类（同余类），第 $i$ 类是所有除以 $m$ 余 $i$ 的整数。它们构成 剩余类环 $\mathbb{Z}_m=\set{[0],[1],\dots,[m-1]}$，环上的加法和乘法就是上面「运算保持」赋予的。

完全剩余系

从每个剩余类里各取一个代表，凑成的 $m$ 个数（模 $m$ 两两不同余），称为 完全剩余系（Complete Residue System）。最常用的是 $\set{0,1,\dots,m-1}$。

简化剩余系

完全剩余系里 与 $m$ 互素 的那些代表，构成 简化剩余系（Reduced Residue System，也叫既约剩余系）。它的元素个数记为 欧拉函数 $\varphi(m)$。

提示

简化剩余系为什么重要？因为只有与 $m$ 互素的数在模 $m$ 下才「可逆」（存在乘法逆元）。这些可逆元在乘法下自成一个封闭系统——简化剩余系对乘法封闭：互素的两个数之积仍与 $m$ 互素。欧拉定理正是建立在这个系统上的。

欧拉函数

$\varphi(m)$ 表示 $\set{1,2,\dots,m}$ 中与 $m$ 互素的整数个数。

公式

$$\varphi(m)=m\prod_{p\mid m}\left(1-\frac{1}{p}\right)$$

其中 $p$ 取遍 $m$ 的不同素因子。直觉上：从 $m$ 个数出发，每个素因子 $p$ 都「筛掉」其中 $\frac1p$ 的比例（即 $p$ 的倍数），各素因子互相独立地筛，乘起来就是剩下的占比。

性质

• $\varphi(p)=p-1$（$p$ 为素数，除 $p$ 自己外全都互素）。
• $\varphi(p^k)=p^k-p^{k-1}$。
• 积性：$\gcd(a,b)=1\Rightarrow\varphi(ab)=\varphi(a)\varphi(b)$。

更多性质详见 积性函数。

三大定理

费马小定理

设 $p$ 是素数，$\gcd(a,p)=1$，则：

$$a^{p-1}\equiv 1\pmod p$$

更一般地，对 任意 整数 $a$ 都有 $a^p\equiv a\pmod p$（不要求互素）。

直觉上为什么成立？把简化剩余系 $\set{1,2,\dots,p-1}$ 每个元素都乘以 $a$，由于 $a$ 与 $p$ 互素，乘出来的 $\set{a,2a,\dots,(p-1)a}$ 模 $p$ 恰好还是原来那 $p-1$ 个数（只是被打乱了顺序）。于是两组的乘积模 $p$ 相等：$a^{p-1}(p-1)!\equiv(p-1)!\pmod p$，约去 $(p-1)!$（它与 $p$ 互素）即得结论。

例：用费马小定理速算 $3^{100}\bmod 7$。$7$ 是素数、$\gcd(3,7)=1$，故 $3^6\equiv 1\pmod 7$。把指数对 $6$ 取模：$100=6\times 16+4$，于是

$$3^{100}=\bigl(3^6\bigr)^{16}\cdot 3^4\equiv 1^{16}\cdot 3^4=81\equiv 4\pmod 7$$

（$81=7\times 11+4$。）一步就把指数从 $100$ 压到 $4$，比快速幂还快。

欧拉定理

费马小定理的推广，把素数模换成任意模。设 $\gcd(a,m)=1$，则：

$$a^{\varphi(m)}\equiv 1\pmod m$$

证明思路与上面如出一辙，只是把整个简化剩余系（共 $\varphi(m)$ 个元素）乘以 $a$ 后重新排列。当 $m=p$ 时 $\varphi(p)=p-1$，正好退化为费马小定理。

提示

欧拉定理最实用的推论是 降幂：求 $a^N\bmod m$ 时，若 $\gcd(a,m)=1$，可以把指数 $N$ 对 $\varphi(m)$ 取模，即 $a^N\equiv a^{N\bmod\varphi(m)}\pmod m$，瞬间把天文数字的指数压到 $\varphi(m)$ 以内。这正是 RSA 加密里「公钥指数」与「私钥指数」互逆的数学根基。（当 $a$ 与 $m$ 不互素时，需要用扩展欧拉定理处理。）

例：求 $7^{222}\bmod 10$。模 $10$ 不是素数，用欧拉定理：$\varphi(10)=\varphi(2)\varphi(5)=1\times 4=4$，且 $\gcd(7,10)=1$，故 $7^4\equiv 1\pmod{10}$。指数对 $4$ 取模 $222=4\times 55+2$，于是

$$7^{222}\equiv 7^{2}=49\equiv 9\pmod{10}$$

即 $7^{222}$ 的个位数字是 $9$。「求末位」就是模 $10$，正是降幂的典型用场。

威尔逊定理

它给出了素数的一个充要刻画：$p$ 是素数当且仅当

$$(p-1)!\equiv -1\pmod p$$

直觉上，$\set{1,2,\dots,p-1}$ 里每个元素都能在模 $p$ 下找到自己的逆元，绝大多数和它的逆元配成一对、乘积为 $1$；唯一「自己是自己逆元」的只有 $1$ 和 $p-1$（即 $-1$）。配对相消后只剩下 $1\cdot(p-1)\equiv-1$。理论价值大于计算价值——阶乘增长太快，不适合用来实际判素。

例：在 $p=7$ 上验证，并看清配对。逆元配对为 $2\cdot 4\equiv 1$、$3\cdot 5\equiv 1\pmod 7$，自逆的是 $1$ 和 $6$。于是

$$6!=1\cdot(2\cdot 4)\cdot(3\cdot 5)\cdot 6\equiv 1\cdot 1\cdot 1\cdot 6=6\equiv-1\pmod 7$$

确实 $(p-1)!\equiv-1$。反观合数 $m=6$：$5!=120=6\times 20\equiv 0\pmod 6$，不是 $-1$——合数处阶乘里会凑出模 $m$ 为 $0$ 的因子，这正是威尔逊定理能判素的根据。

快速幂取模

求 $a^n\bmod m$ 时，若把 $a$ 自乘 $n$ 次要 $O(n)$ 步，指数一大就崩。快速幂（Fast Exponentiation）用 $n$ 的 二进制分解 把它压到 $O(\log n)$：

$$a^n=\prod_{k:\,n\text{ 的第 }k\text{ 位为 }1}a^{2^k}$$

具体做法是边平方边判位：维护一个底数不断自乘平方（得到 $a,a^2,a^4,a^8,\dots$），扫描 $n$ 的每一位二进制，遇到 $1$ 就把当前平方值乘进答案，全程对 $m$ 取模。这是 RSA、ECDSA、矩阵幂等几乎所有「大指数取模」场景的基础操作，也是下面解同余方程的常用零件。

例：用快速幂算 $7^{100}\bmod 13$。先把指数二进制化 $100=(1100100)_2=64+32+4$，即用到 $7^{64},7^{32},7^4$。逐次平方并随时对 $13$ 取模：

$$\begin{aligned} 7^1&\equiv 7 \\ 7^2&\equiv 49\equiv 10 \\ 7^4&\equiv 10^2=100\equiv 9 \\ 7^8&\equiv 9^2=81\equiv 3 \\ 7^{16}&\equiv 3^2=9 \\ 7^{32}&\equiv 9^2=81\equiv 3 \\ 7^{64}&\equiv 3^2=9 \end{aligned}\pmod{13}$$

只把指数二进制为 $1$ 的那几项（$7^{64},7^{32},7^4$）乘起来：

$$7^{100}\equiv 7^{64}\cdot 7^{32}\cdot 7^4\equiv 9\times 3\times 9=243\equiv 9\pmod{13}$$

（$243=13\times 18+9$。）所以 $7^{100}\equiv 9\pmod{13}$。整个过程只做了 $6$ 次平方和 $2$ 次乘法，远少于朴素的 $99$ 次乘法。

一次同余方程

形式：

$$ax\equiv b\pmod m$$

解的存在性：有解 $\iff\gcd(a,m)\mid b$。这和 二元一次不定方程 的可解条件是同一件事——$ax\equiv b\pmod m$ 等价于 $ax+my=b$ 有整数解。

解的个数：若有解，则模 $m$ 意义下恰有 $\gcd(a,m)$ 个互不同余的解。

例：解 $3x\equiv 6\pmod 9$。$\gcd(3,9)=3$，而 $3\mid 6$，故有解，且模 $9$ 下有 $3$ 个解。两边连同模数一起除以 $3$（约去公因子时模数也要除）得 $x\equiv 2\pmod 3$，回到模 $9$ 即 $x\equiv 2,5,8\pmod 9$。可逐一验证：$3\times 2=6$、$3\times 5=15\equiv 6$、$3\times 8=24\equiv 6\pmod 9$，三个都对。

例：解 $5x\equiv 3\pmod{11}$。$\gcd(5,11)=1$，唯一解。先求 $5$ 的逆元——找 $5x\equiv 1$：试 $5\times 9=45\equiv 1\pmod{11}$，故 $5^{-1}\equiv 9$。于是 $x\equiv 9\times 3=27\equiv 5\pmod{11}$。验算 $5\times 5=25\equiv 3\pmod{11}$，正确。

模逆元

当 $\gcd(a,m)=1$ 时，方程 $ax\equiv 1\pmod m$ 有唯一解，这个 $x$ 称为 $a$ 的 模逆元（Modular Inverse），记 $a^{-1}\bmod m$。有了逆元，一般方程 $ax\equiv b$ 的解就是 $x\equiv a^{-1}b\pmod m$，相当于在模运算里实现了「除法」。

求逆元有两条常用途径：

• 扩展欧几里得：解 $ax+my=1$，求出的 $x$ 就是逆元，对任意互素的 $a,m$ 都适用。
• 费马小定理：当 $m$ 为素数时，$a^{-1}\equiv a^{m-2}\pmod m$（因为 $a\cdot a^{m-2}=a^{m-1}\equiv1$），配合快速幂即可。

例（扩欧法）：求 $3$ 模 $7$ 的逆元，即解 $3x+7y=1$。辗转相除 $7=2\times 3+1$，故 $1=7-2\times 3$，对照得 $x=-2,\ y=1$。于是 $3^{-1}\equiv-2\equiv 5\pmod 7$，验算 $3\times 5=15\equiv 1\pmod 7$，正确。扩欧的好处是 模数不必为素数，只要 $\gcd(a,m)=1$ 就能用。

例（费马法）：求 $3$ 模 $7$ 的逆元。$7$ 为素数，故 $3^{-1}\equiv 3^{7-2}=3^5\pmod 7$。算 $3^5$：$3^2=9\equiv 2$，$3^4\equiv 2^2=4$，$3^5\equiv 4\times 3=12\equiv 5\pmod 7$，与扩欧法结果一致。费马法写起来更短，但要求模数是素数、且要做一次快速幂。

中国剩余定理

设模数 $m_1,m_2,\dots,m_k$ 两两互素，考虑同余方程组：

$$\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \\ \vdots \\ x\equiv a_k\pmod{m_k} \end{cases}$$

则它在模 $M=m_1m_2\cdots m_k$ 意义下有 唯一解。这就是 中国剩余定理（Chinese Remainder Theorem，CRT）。

提示

CRT 的直觉是「分别定位，再拼合」。把一个数想象成由它在各个模下的余数 $(a_1,\dots,a_k)$ 共同决定的一组坐标。两两互素保证了这组坐标 无冗余也无遗漏：在 $0\sim M-1$ 范围内，每一组可能的余数恰好对应唯一一个数。所以解方程组就是「已知各坐标，反求那个数」，必然有且只有一个答案。它在算法上还能反向用——把模 $M$ 的运算拆成几个小模并行做，最后拼回来。

构造解

构造的妙处在于「凑出只在一个方程里起作用、对其他方程透明」的项。令 $M_i=M/m_i$，则 $M_i$ 是除 $m_i$ 外所有模的倍数，因此 $M_i\equiv 0\pmod{m_j}\,(j\ne i)$。由于 $\gcd(M_i,m_i)=1$，可求出 $M_i$ 模 $m_i$ 的逆元 $M_i^{-1}$。于是：

$$x\equiv\sum_{i=1}^{k}a_i\,M_i\,M_i^{-1}\pmod M$$

第 $i$ 项 $a_iM_iM_i^{-1}$ 在模 $m_i$ 下等于 $a_i$（因为 $M_iM_i^{-1}\equiv1$），在模 $m_j\,(j\ne i)$ 下等于 $0$（因为带着因子 $M_i$）。每一项各管一个方程，互不干扰，加起来就同时满足全部条件。

完整算例：物不知数

《孙子算经》的「物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问几何。即解

$$x\equiv 2\pmod 3,\quad x\equiv 3\pmod 5,\quad x\equiv 2\pmod 7$$

模数 $3,5,7$ 两两互素，$M=3\times 5\times 7=105$。逐项算 $M_i$ 与其逆元：

$$\begin{aligned} &M_1=105/3=35,\quad 35\equiv 2\pmod 3,\quad M_1^{-1}\equiv 2^{-1}\equiv 2\pmod 3 \\ &M_2=105/5=21,\quad 21\equiv 1\pmod 5,\quad M_2^{-1}\equiv 1\pmod 5 \\ &M_3=105/7=15,\quad 15\equiv 1\pmod 7,\quad M_3^{-1}\equiv 1\pmod 7 \end{aligned}$$

（求逆元：$2\times 2=4\equiv 1\pmod 3$ 故 $2^{-1}\equiv 2$；另两个本身就 $\equiv 1$，逆元为 $1$。）代入构造式：

$$\begin{aligned} x&\equiv a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+a_3M_3M_3^{-1} \\ &=2\times 35\times 2+3\times 21\times 1+2\times 15\times 1 \\ &=140+63+30=233\equiv 23\pmod{105} \end{aligned}$$

（$233=105\times 2+23$。）所以最小正整数解是 $\boxed{23}$，全部解为 $x\equiv 23\pmod{105}$。验算：$23=3\times 7+2$、$23=5\times 4+3$、$23=7\times 3+2$，三个余数全对。这就是口诀「三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知」里那三个系数 $70,21,15$ 的来历——$70=a_1$ 项的 $M_1M_1^{-1}=35\times 2$。

高次同余与原根

形如 $x^k\equiv a\pmod m$ 的方程属于 高次同余，远比一次复杂。研究它的关键工具是 原根（Primitive Root）。

设 $\gcd(a,m)=1$，使 $a^d\equiv1\pmod m$ 成立的最小正整数 $d$ 称为 $a$ 模 $m$ 的 阶（Order）。由欧拉定理 $d\mid\varphi(m)$。若某个 $g$ 的阶恰好达到最大值 $\varphi(m)$，就称 $g$ 是模 $m$ 的一个 原根。

原根存在时（仅当 $m=1,2,4,p^k,2p^k$，$p$ 为奇素数），它的幂 $g^0,g^1,\dots,g^{\varphi(m)-1}$ 会 不重不漏地跑遍整个简化剩余系。这相当于给乘法群配了一把「对数尺」：乘法变成指数相加，高次同余 $x^k\equiv a$ 就化归为一次同余，可解。这套「离散对数」也是 Diffie–Hellman 密钥交换的基础。

例：求模 $7$ 的一个原根。$\varphi(7)=6$，$6$ 的真因子里要检验的是 $\frac{6}{2}=3$ 和 $\frac{6}{3}=2$——只需验 $g^2\not\equiv 1$ 且 $g^3\not\equiv 1$，就能断定阶恰为 $6$（不必逐个算到 $6$）。试 $g=3$：$3^2=9\equiv 2\ne 1$，$3^3=27\equiv 6\ne 1\pmod 7$，两条都过，故 $3$ 是原根。验证其幂跑遍简化剩余系：

$$3^1\equiv 3,\ 3^2\equiv 2,\ 3^3\equiv 6,\ 3^4\equiv 4,\ 3^5\equiv 5,\ 3^6\equiv 1\pmod 7$$

$\set{3,2,6,4,5,1}$ 恰好就是 $\set{1,2,3,4,5,6}$，无重复、无遗漏。顺带一提 $g=2$ 不是原根：$2^3=8\equiv 1\pmod 7$，阶只有 $3$。

提示

找原根的标准做法 不是 把 $g^1,g^2,\dots$ 一直算到 $\varphi(m)$，而是：分解 $\varphi(m)=\prod q_i^{e_i}$，对每个素因子 $q_i$ 检验 $g^{\varphi(m)/q_i}\not\equiv 1\pmod m$。只要所有这些都不为 $1$，$g$ 的阶就必然是满的 $\varphi(m)$。这把检验量从 $\varphi(m)$ 次降到素因子个数次。

二次剩余

最简单的高次情形是 $k=2$：问 $x^2\equiv a\pmod p$ 有没有解。若有解，称 $a$ 是模 $p$ 的 二次剩余（Quadratic Residue，QR）；否则称 二次非剩余。

对奇素数 $p$，简化剩余系里恰好一半是二次剩余、一半不是。判定用 勒让德符号（Legendre Symbol）：

$$\left(\frac{a}{p}\right)=\begin{cases}\ \ 1,&a\text{ 是二次剩余} \\ -1,&a\text{ 是二次非剩余} \\ \ \ 0,&p\mid a\end{cases}$$

它可由 欧拉判别法 算出：

$$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$$

直觉上，$a^{\frac{p-1}{2}}$ 是费马小定理 $a^{p-1}\equiv1$ 的「平方根」，只能取 $\pm1$；取 $+1$ 当且仅当 $a$ 本身开得出平方根。更高效的判定依赖 二次互反律——高斯称之为「黄金定理」，是数论的标志性成果之一。

例：先把模 $7$ 的二次剩余列全。对 $x=1\sim 6$ 算 $x^2\bmod 7$：

$$1^2\equiv 1,\ 2^2\equiv 4,\ 3^2\equiv 2,\ 4^2\equiv 2,\ 5^2\equiv 4,\ 6^2\equiv 1\pmod 7$$

去重得二次剩余为 $\set{1,2,4}$，非剩余为 $\set{3,5,6}$，恰好各 $3$ 个（即 $\frac{p-1}{2}$），印证「一半是一半不是」。注意 $x$ 与 $-x$ 平方相同，故剩余总成对出现。

例：用欧拉判别法判 $3$ 是否为模 $7$ 的二次剩余。算 $3^{\frac{7-1}{2}}=3^3=27\equiv 6\equiv-1\pmod 7$，得 $\left(\frac{3}{7}\right)=-1$，所以 $3$ 是 非剩余，$x^2\equiv 3\pmod 7$ 无解——与上面列出的剩余表 $\set{1,2,4}$ 不含 $3$ 一致。再判 $2$：$2^3=8\equiv 1\pmod 7$，故 $\left(\frac{2}{7}\right)=1$，$2$ 是剩余，确有 $3^2\equiv 4^2\equiv 2$。

应用一瞥

同余几乎渗透在每个数论场景里：

• 整除判定：判断一个数能否被 $3,9,11$ 整除的「各位数字求和」法则，本质是 $10\equiv1\pmod9$、$10\equiv-1\pmod{11}$。
• 大整数运算：把大数拆成多个小模（两两互素），用 CRT 并行计算再拼回，是高精度库的常用加速。
• 公钥密码：RSA 的加解密就是模 $n$ 下的幂运算，其正确性由欧拉定理保证，效率由快速幂和 CRT 支撑。