同余

同余（congruence）用来表示两个整数除以同一个正整数时余数相同。例如 17 和 5 除以 12 都余 5，记作 $17 \equiv 5 (\mod 12)$ ，读作“17 与 5 模 12 同余”。这里的 12 称为模数。

十二小时钟面提供了直观例子：从 5 点经过 12 小时，指针回到相同位置。17 与 5 的完整数值不同，但若只记录钟面位置，它们包含相同的信息。

相同余数，就是相差整倍数

设整数 a、b 除以正整数 m 的余数都是 r，即 $a = q m + r, b = q^{'} m + r .$ 相减便有 $a - b = (q - q^{'}) m$ ，所以差被 m 整除。反过来，若两个数相差 m 的整数倍，带余除法中可以把这个倍数归入商，余数就不改变。因此同余可以精确定义为 $a \equiv b (\mod m) ⟺ m ∣ (a - b) .$ 整除符号 $∣$ 的含义见整数整除。

例如 $- 1 \equiv 11 (\mod 12)$ ，因为二者相差 −12。余数通常选在 $0, 1, \dots, m - 1$ 中，但同余式右边可以使用其他代表，如 $17 \equiv - 7 (\mod 12)$ 。这类似于从钟面 12 点往前退一格，可以用 −1 表示，也可以用 11 表示。

下图把一整圈分为 12 格，以 0 为起点。左图先顺时针走完整一圈，再走 5 格，17 与 5 停在同一位置；右图逆时针退一格，−1 停在标为 11 的位置。圈内的完整转动可以省去，但方向与最后位置仍被保留。

17 与 5、−1 与 11 各自相差一个完整的 12 格周期。

记号 $17 mod 1 2 = 5$ 表示取标准余数；同余符号则是在比较两个整数。对负数取余时，程序语言可能采用不同的商约定，数学同余仍由“差是模数的倍数”决定。下文以 $m \geq 2$ 为主；模 1 时全部整数同余，只有一种余数。

为什么可以先化小，再计算

从 5 点再过 17 小时，可以先把 17 小时看成“完整一圈再多 5 小时”，只在钟面上前进 5 格，结果是 10 点。这对应 $5 + 17 \equiv 5 + 5 = 10 (\mod 12) .$ 减法也一样，减去一个完整周期不会改变最终位置。

一般地，若 $a \equiv a^{'} (\mod m)$ 、 $b \equiv b^{'} (\mod m)$ ，那么 $a + b \equiv a^{'} + b^{'}, a - b \equiv a^{'} - b^{'} (\mod m) .$ 原因是相减后只剩下 m 的整数倍。乘法也保持同余，因为 $a b - a^{'} b^{'} = (a - a^{'}) b + a^{'} (b - b^{'}) .$ 右边两项各自含有一个被 m 整除的因子，所以乘积之差也被 m 整除。由此，整数加减乘以及非负整数次幂，都可以边算边取余。

例如求 $7^{100}$ 除以 13 的余数，不必先写出整个大数。先连续平方： $\begin{matrix} 7^{2} & = 49 \equiv 10, \\ 7^{4} & \equiv 1 0^{2} = 100 \equiv 9, \\ 7^{8} & \equiv 9^{2} = 81 \equiv 3 (\mod 13) . \end{matrix}$ 再把已得到的幂相乘， $7^{12} = 7^{8} \cdot 7^{4} \equiv 3 \cdot 9 = 27 \equiv 1$ 。由于 $100 = 12 \cdot 8 + 4$ ， $7^{100} = (7^{12})^{8} 7^{4} \equiv 1^{8} \cdot 9 = 9 (\mod 13) .$ 每次计算后都只留下小于 13 的代表数，中间数字便保持很小。

这里能把指数中的 12 个一组，依据的是刚刚算出的 $7^{12} \equiv 1$ ，并非把指数也随意模 13。更一般的重复平方法将指数写成若干个 2 的幂之和，再选择连续平方得到的结果相乘。

除法为何需要额外条件

同余中的乘法可能把不同余数合并。例如模 6 时， $2 \cdot 1 \equiv 2 \cdot 4 (\mod 6),$ 但 1 与 4 并不同余。乘上 2 以后，两边之差由 3 变成 6，才成为模数的倍数；直接约去 2 会丢失这一区别。

正确的消去结论会同时考虑乘数和模数。若 $c a \equiv c b (\mod m)$ ，设 $d = gcd (c, m)$ ，则 $a \equiv b (\mod m / d) .$ 证明从 $m ∣ c (a - b)$ 出发：把 m、c 的共同因子 d 除去后， $m / d$ 与 $c / d$ 互素，所以由互素消去性质， $m / d$ 整除 $a - b$ 。上例约去 2 后得到 $1 \equiv 4 (\mod 3)$ ，模数也从 6 变为 3。

如果乘数与模数互素，就可以在不改变模数的情况下消去。更方便的做法是寻找一个数 u，使 $a u \equiv 1 (\mod m) .$ u 叫 a 的模逆元。两边乘 u，便能撤销乘 a 的作用。

逆元存在恰好等价于 $gcd (a, m) = 1$ 。若逆元存在，则有 $a u - m k = 1$ ，a 与 m 的任何共同因数都必须整除 1；反过来，若它们互素，裴蜀等式 $a u + m v = 1$ 直接给出逆元 u。

完整求解一个同余方程

求所有整数 x，使 $14 x \equiv 30 (\mod 100) .$ 这表示 14x 除以 100 余 30。14 与 100 的最大公因数是 2，而且 2 整除 30，因此可以同时除去这个共同因子，得到 $7 x \equiv 15 (\mod 50) .$ 7 与 50 已经互素。由 $50 = 7 \cdot 7 + 1$ ，可写 $1 = 50 - 7 \cdot 7$ ，所以 7 的逆元是 −7，或等价地用 43 表示。验证有 $7 \cdot 43 = 301 \equiv 1 (\mod 50)$ 。

在约化的方程两边乘 43： $x \equiv 43 \cdot 15 = 645 \equiv 45 (\mod 50) .$ 于是全部整数解为 $x = 45 + 50 t$ ，其中 $t \in ℤ$ 。若用模 100 的代表表示，答案有两类： $x \equiv 45 或 95 (\mod 100) .$ 代回后 $14 \cdot 45 = 630$ ， $14 \cdot 95 = 1330$ ，都余 30。两个解类的出现来自约化后的周期是 50，而原来按 100 分组，一个周期内包含两次这样的解。

一般方程 $a x \equiv b (\mod m)$ 等价于某个整数方程 $a x + m y = b$ ，因此有解当且仅当 $d = gcd (a, m)$ 整除 b。有解时，除以 d 后在模 $m / d$ 下得到一个解类，在原模数 m 下则得到 d 个解类。例如把本题右端换成 31，由于 2 不整除 31，方程便无解。

三条余数信息怎样合成

《孙子算经》中的一个问题问：一个数除以 3 余 2，除以 5 余 3，除以 7 余 2，它可以是多少？

先使用除以 5 的条件，写成 $x = 3 + 5 t$ 。再代入除以 3 的条件，因为 $3 + 5 t \equiv 2 t (\mod 3)$ ，得到 $2 t \equiv 2 (\mod 3)$ ，所以 $t = 1 + 3 s$ 。代回得 $x = 3 + 5 (1 + 3 s) = 8 + 15 s .$ 这样表达式已经同时满足前两条条件。最后对 7 取余： $8 + 15 s \equiv 1 + s \equiv 2 (\mod 7),$ 故 $s = 1 + 7 k$ ，得到 $x = 8 + 15 (1 + 7 k) = 23 + 105 k, k \in ℤ .$ 23 满足三条条件；每增加 $105 = 3 \cdot 5 \cdot 7$ ，三个余数都不变。若要求最小正数，答案是 23；若没有大小范围，便有上述无限多个整数解。

中国剩余定理把这个现象推广：若若干模数两两互素，则任意指定的一组余数都能同时实现，而且全部解恰好构成模这些模数之积的一个解类。

两个模数时的构造证明

设 m、n 互素，要求 $x \equiv a (\mod m)$ 、 $x \equiv b (\mod n)$ 。裴蜀等式提供 $u m + v n = 1$ 。其中 vn 模 m 余 1、模 n 余 0；um 恰好相反。于是取 $x = a v n + b u m .$ 模 m 时，第二项为零，第一项为 a；模 n 时，第一项为零，第二项为 b。这证明解存在。

若 x、x′ 都是解，其差同时被 m、n 整除。写 $x - x^{'} = m r$ ，由 n 与 m 互素， $n ∣ m r$ 推出 $n ∣ r$ ，所以 $m n ∣ (x - x^{'})$ 。反过来，给一个解加上 mn 的任意倍数，两个余数都不变。这就证明全部解正好相差 mn 的倍数。多个两两互素的模数，可以逐步合并。

模数有共同因子时，要求可能冲突。例如模 4 余 1 要求 x 为奇数，模 6 余 2 却要求 x 为偶数，因而无解。一般两个模数的条件相容，当且仅当它们的最大公因数整除两余数之差。相容时，解的周期为两模数的最小公倍数，共同因子所包含的信息只计一次。

为什么数字和能判断整除

一个十进制非负整数由各位数字乘上相应位值组成。例如 $45728 = 4 \cdot 1 0^{4} + 5 \cdot 1 0^{3} + 7 \cdot 1 0^{2} + 2 \cdot 10 + 8.$ 由于 $10 \equiv 1 (\mod 9)$ ，每个十的非负整数次幂都模 9 余 1。因此 $45728 \equiv 4 + 5 + 7 + 2 + 8 = 26 \equiv 8 (\mod 9) .$ 所以 45728 不能被 9 整除。对任何十进制非负整数，同样的逐项化简都成立，便得到“数字和能被 9 整除，原数也能被 9 整除”的判据。模 3 时也有 $10 \equiv 1$ ，理由相同。

模 11 时则有 $10 \equiv - 1$ ，所以从个位起，位值的余数依次是 1、−1、1、−1……。例如 $12321 \equiv 1 - 2 + 3 - 2 + 1 = 1 (\mod 11),$ 故它不能被 11 整除。起始符号取反会使整个结果变号，不影响是否为零，但会改变所报告的具体余数。

对负整数，可先处理其绝对值，再加上负号。例如 12 的数字和是 3，但 $- 12 \equiv - 3 \equiv 6 (\mod 9)$ ，余数不是 3。

同余还能用于检查运算。若一个加法等式两边模 9 的结果不同，等式一定错了；结果相同，则仍可能相差 9、18 等倍数。校验保留了余数，却没有保留完整数值。若另外已知两边之差的绝对值小于 9，“差是 9 的倍数”才会迫使差为零。

余数类与信息的范围

所有模 m 与 a 同余的整数组成一个剩余类： $[a]_{m} = {a + k m : k \in ℤ} .$ 例如模 5 的零类是全部 5 的倍数。模 5 共有五个不同的类，可以用 0、1、2、3、4 代表；每个类却含有无限多个整数。

同余具有自反性、对称性和传递性，分别来自 $a - a = 0$ 、 $b - a = - (a - b)$ 和 $a - c = (a - b) + (b - c)$ 。因此它是一种等价关系。两类若有共同元素，就可以通过这个元素推出两位代表同余，因而两类完全相同；否则它们不相交。这样，全部整数被整齐分为 m 类。

类的加法和乘法可以由代表数计算，因为前面已经证明更换同余代表不影响结果。模 6 时，非零的 2 类与 3 类相乘却为零类，这也解释了为什么非零代表不一定有乘法逆元。剩余类在加法下形成循环群，模逆元则挑出哪些类能够进行可逆的乘法。

余数信息有时可以配合范围确定原数。例如已经得到 $x \equiv 23 (\mod 105)$ ，再知道 $0 \leq x \leq 100$ ，便只有 23 一个候选；若范围是 0 到 200，则还有 128。选择 23 或 −82 作为代表都表示同一类，代表的大小并不是整个剩余类的内在大小。

历史

《孙子算经》记载了上面的三、五、七余数问题。文本的成书年代及作者生平仍有不确定之处；MacTutor：Sun Zi整理了相关文献与年代判断。

Gauss 在 1801 年出版《算术研究》，把同余作为系统组织整数论的重要语言。书目可见美国国会图书馆的原书记录；Gauss 的学术传记说明了这种表述在书中的作用。从按组计数反求总数，到用统一符号处理整除、幂与方程，余数问题逐渐形成了系统理论。

参考资料

Thomas W. Judson，Abstract Algebra: Theory and Applications：整数与剩余类。
Karl-Dieter Crisman，Number Theory: In Context and Interactive：同余、模幂和中国剩余定理。
J. J. O’Connor、E. F. Robertson，Sun Zi。
Library of Congress，Disquisitiones arithmeticae，1801。
相关条目：整数整除、素数、集合、群、逻辑。