同余：修订间差异

2026年9月20日 (日) 07:17的最新版本

同余（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。
相关条目：整数整除、素数、集合、群、逻辑。

@@ 第1行： / 第1行： @@
-'''同余'''（congruence modulo an integer）是按整数除以同一个正整数后的余数来比较它们的关系。固定模数 <math>m\ge2</math>，若 <math>m\mid(a-b)</math>，就写作 <math>a\equiv b\pmod m</math>，读作“<math>a</math> 与 <math>b</math> 模 <math>m</math> 同余”。这等价于二者按非负余数约定除以 <math>m</math> 后余数相同。同余保留与某种周期有关的信息，舍去完整整数的大小信息，是[[整数整除]]、周期计算和代数结构之间的桥梁。
+'''同余'''（congruence）用来表示两个整数除以同一个正整数时余数相同。例如 17 和 5 除以 12 都余 5，记作 <math>17\equiv5\pmod{12}</math>，读作“17 与 5 模 12 同余”。这里的 12 称为'''模数'''。
-== 钟面留下了哪些信息 ==
+十二小时钟面提供了直观例子：从 5 点经过 12 小时，指针回到相同位置。17 与 5 的完整数值不同，但若只记录钟面位置，它们包含相同的信息。
-十二小时钟面上，十五时与三时指向相同刻度，因为两者相差十二；增加二十四小时也不改变刻度。这个比较不表示十五与三作为整数相等，而是说在“只关心十二小时周期位置”的问题中，它们无法区分。模数说明当前舍去了哪一部分信息，不能在计算中无声更换。
-同样，<math>17\equiv5\pmod{12}</math>，而 <math>-1\equiv11\pmod{12}</math>。负数并没有特殊障碍，因为差仍可被模数整除。使用代表数时常选零到 <math>m-1</math>，但任何同余整数都可代表同一类别；为了心算方便，把十一写成负一有时更简洁。
+== 相同余数，就是相差整倍数 ==
+设整数 a、b 除以正整数 m 的余数都是 r，即
+<math display="block">a=qm+r,\qquad b=q'm+r.</math>
+相减便有 <math>a-b=(q-q')m</math>，所以差被 m 整除。反过来，若两个数相差 m 的整数倍，带余除法中可以把这个倍数归入商，余数就不改变。因此同余可以精确定义为
+<math display="block">a\equiv b\pmod m
+\quad\Longleftrightarrow\quad m\mid(a-b).</math>
+整除符号 <math>\mid</math> 的含义见[[整数整除]]。
-“取模得到余数”是一种产生代表数的操作，“同余”则是两个整数之间的关系。例如 <math>17\bmod12=5</math> 表示所选非负余数，而同余式可写成 <math>17\equiv-7\pmod{12}</math>，右侧不必是标准余数。程序语言对负数取余的约定可能不同，不能据此改变数学同余关系本身。
+例如 <math>-1\equiv11\pmod{12}</math>，因为二者相差 −12。余数通常选在 <math>0,1,\ldots,m-1</math> 中，但同余式右边可以使用其他代表，如 <math>17\equiv-7\pmod{12}</math>。这类似于从钟面 12 点往前退一格，可以用 −1 表示，也可以用 11 表示。
-模数一也可以定义，此时所有整数同余，只有一个剩余类；本条主要采用 <math>m\ge2</math>，以保留非平凡的区分。模数零不按普通余数运算处理。明确这些边界，可以避免把定义式中的整除和常见程序操作直接混为一谈。
+下图把一整圈分为 12 格，以 0 为起点。左图先顺时针走完整一圈，再走 5 格，17 与 5 停在同一位置；右图逆时针退一格，−1 停在标为 11 的位置。圈内的完整转动可以省去，但方向与最后位置仍被保留。
-== 剩余类把整数分成互不重叠的类别 ==
+[[File:Gezhi-teaching-foundation-congruence-clock.svg|frame|center|alt=两个模十二钟面，左图顺时针一圈加五格停在五，右图从零逆时针一格停在十一|17 与 5、−1 与 11 各自相差一个完整的 12 格周期。]]
-模 <math>m</math> 同余是等价关系。每个整数与自身同余，因为差为零；若 <math>a-b</math> 是模数的倍数，<math>b-a</math> 也是，所以关系对称；若 <math>a-b</math> 与 <math>b-c</math> 都是模数的倍数，它们的和 <math>a-c</math> 也是，所以关系传递。三条性质保证按同余分组不会出现互相冲突的归类。
-整数 <math>a</math> 所属的剩余类记为 <math>[a]_m</math>，是所有 <math>a+km</math> 的集合，其中 <math>k</math> 遍历整数。模五共有五类，可以用零、一、二、三、四代表。每一类本身都无限，例如零类包含所有五的倍数；“只有五类”不是说只有五个整数。
+记号 <math>17\bmod12=5</math> 表示取标准余数；同余符号则是在比较两个整数。对负数取余时，程序语言可能采用不同的商约定，数学同余仍由“差是模数的倍数”决定。下文以 <math>m\ge2</math> 为主；模 1 时全部整数同余，只有一种余数。
-两个剩余类要么相同，要么完全不相交。若某个整数同时在两类中，由对称性与传递性可推出两位代表同余，因此整个类别相同。这个事实把“相同余数”提升为严格的集合划分，也连接到[[集合]]中的等价分类思想。以后群的陪集和商结构会采用类似方式，但必须额外检查运算是否与分组相容。
+== 为什么可以先化小，再计算 ==
+从 5 点再过 17 小时，可以先把 17 小时看成“完整一圈再多 5 小时”，只在钟面上前进 5 格，结果是 10 点。这对应
+<math display="block">5+17\equiv5+5=10\pmod{12}.</math>
+减法也一样，减去一个完整周期不会改变最终位置。
-当只需要周期位置时，可以把所有整数压缩到有限个类别；当需要实际数量时，这种压缩会丢失信息。例如模七知道一个活动安排在周几，不能据此知道具体日期。恢复整数通常还需要取值范围、多个模数条件或其他信息。
+一般地，若 <math>a\equiv a'\pmod m</math>、<math>b\equiv b'\pmod m</math>，那么
+<math display="block">a+b\equiv a'+b',\qquad a-b\equiv a'-b'\pmod m.</math>
+原因是相减后只剩下 m 的整数倍。乘法也保持同余，因为
+<math display="block">ab-a'b'=(a-a')b+a'(b-b').</math>
+右边两项各自含有一个被 m 整除的因子，所以乘积之差也被 m 整除。由此，整数加减乘以及非负整数次幂，都可以边算边取余。
-== 加减乘为什么合法，除法为什么危险 ==
+例如求 <math>7^{100}</math> 除以 13 的余数，不必先写出整个大数。先连续平方：
-若 <math>a\equiv a'\pmod m</math>、<math>b\equiv b'\pmod m</math>，则加法、减法和乘法都保持同余。加减法的理由是两组差仍为模数倍数；乘法则利用
+<math display="block">\begin{aligned}
-<math display="block">ab-a'b'=(a-a')b+a'(b-b').</math>
+^2&=49\equiv10,\\
-右侧每项都含有一个被模数整除的因子，因此总差也被整除。这证明可以在计算中随时把整数换成较小的同余代表，而不会改变最终余数。
+^4&\equiv10^2=100\equiv9,\\
+^8&\equiv9^2=81\equiv3\pmod{13}.
+\end{aligned}</math>
+再把已得到的幂相乘，<math>7^{12}=7^8\cdot7^4\equiv3\cdot9=27\equiv1</math>。由于 <math>100=12\cdot8+4</math>，
+<math display="block">7^{100}=(7^{12})^8\,7^4\equiv1^8\cdot9=9\pmod{13}.</math>
+每次计算后都只留下小于 13 的代表数，中间数字便保持很小。
-非负整数次幂与整系数多项式也保持同余，因为它们由有限次加法和乘法构成。必须保留“整系数”或另行解释分母可逆性，不能把带除法的任意表达式直接代入。平方根也不能直接保持唯一性，因为不同剩余类可能有相同平方。
+这里能把指数中的 12 个一组，依据的是刚刚算出的 <math>7^{12}\equiv1</math>，并非把指数也随意模 13。更一般的重复平方法将指数写成若干个 2 的幂之和，再选择连续平方得到的结果相乘。
-例如 <math>2\cdot1\equiv2\cdot4\pmod6</math>，但一与四模六不同余，所以不能简单约去二。问题在于二与六共享因数，乘二后可能把不同类别合并。这与实数中乘非零数不会合并输入的情形不同。把普通等式消去规则原封不动搬来，会丢掉合法解。
+== 除法为何需要额外条件 ==
+同余中的乘法可能把不同余数合并。例如模 6 时，
+<math display="block">2\cdot1\equiv2\cdot4\pmod6,</math>
+但 1 与 4 并不同余。乘上 2 以后，两边之差由 3 变成 6，才成为模数的倍数；直接约去 2 会丢失这一区别。
-正确的消去结论是：若 <math>ca\equiv cb\pmod m</math>，令 <math>d=\gcd(c,m)</math>，则 <math>a\equiv b\pmod{m/d}</math>。证明是把整除式 <math>m\mid c(a-b)</math> 中共同因子 <math>d</math> 除去，剩下的 <math>c/d</math> 与 <math>m/d</math> 互素，再用互素整除性质消去。只有 <math>d=1</math> 时，才可在保持原模数不变的情况下消去。
+正确的消去结论会同时考虑乘数和模数。若 <math>ca\equiv cb\pmod m</math>，设 <math>d=\gcd(c,m)</math>，则
+<math display="block">a\equiv b\pmod{m/d}.</math>
+证明从 <math>m\mid c(a-b)</math> 出发：把 m、c 的共同因子 d 除去后，<math>m/d</math> 与 <math>c/d</math> 互素，所以由互素消去性质，<math>m/d</math> 整除 <math>a-b</math>。上例约去 2 后得到 <math>1\equiv4\pmod3</math>，模数也从 6 变为 3。
-== 模逆元与线性同余方程 ==
+如果乘数与模数互素，就可以在不改变模数的情况下消去。更方便的做法是寻找一个数 u，使
-若整数 <math>a</math> 存在整数 <math>u</math>，使 <math>au\equiv1\pmod m</math>，就称 <math>u</math> 是 <math>a</math> 模 <math>m</math> 的逆元。逆元存在当且仅当 <math>\gcd(a,m)=1</math>。必要性来自任何共同因数都整除一；充分性来自裴蜀等式 <math>ua+vm=1</math>，取模即可。
+<math display="block">au\equiv1\pmod m.</math>
+u 叫 a 的'''模逆元'''。两边乘 u，便能撤销乘 a 的作用。
-例如 <math>50=7\cdot7+1</math>，整理为 <math>1=50-7\cdot7</math>，所以七模五十的逆元是负七，也可用四十三代表。验证 <math>7\cdot43=301\equiv1\pmod{50}</math>。求逆元是在特定模数下撤销乘法，不是普通分数 <math>1/7</math> 的十进制近似。
+逆元存在恰好等价于 <math>\gcd(a,m)=1</math>。若逆元存在，则有 <math>au-mk=1</math>，a 与 m 的任何共同因数都必须整除 1；反过来，若它们互素，裴蜀等式 <math>au+mv=1</math> 直接给出逆元 u。
-线性同余方程 <math>ax\equiv b\pmod m</math> 有解，当且仅当 <math>d=\gcd(a,m)</math> 整除 <math>b</math>。因为原式等价于某个整数方程 <math>ax+my=b</math>，可直接应用[[整数整除]]中的裴蜀判据。若有解，除以 <math>d</math> 并把模数也除以 <math>d</math>，就得到系数与新模数互素的方程，能够通过逆元求解。
+== 完整求解一个同余方程 ==
+求所有整数 x，使
+<math display="block">14x\equiv30\pmod{100}.</math>
+这表示 14x 除以 100 余 30。14 与 100 的最大公因数是 2，而且 2 整除 30，因此可以同时除去这个共同因子，得到
+<math display="block">7x\equiv15\pmod{50}.</math>
+与 50 已经互素。由 <math>50=7\cdot7+1</math>，可写 <math>1=50-7\cdot7</math>，所以 7 的逆元是 −7，或等价地用 43 表示。验证有 <math>7\cdot43=301\equiv1\pmod{50}</math>。
-完整计算 <math>14x\equiv30\pmod{100}</math>。最大公因数为二，确实整除三十，约化后得到 <math>7x\equiv15\pmod{50}</math>。乘以逆元四十三，
+在约化的方程两边乘 43：
 <math display="block">x\equiv43\cdot15=645\equiv45\pmod{50}.</math>
-因此按原模数一百计算有两类解：四十五与九十五。代回分别得到六百三十与一千三百三十，除以一百都余三十。若右端改成三十一，则因二不整除三十一而无解，无须继续试数。
+于是全部整数解为 <math>x=45+50t</math>，其中 <math>t\in\mathbb Z</math>。若用模 100 的代表表示，答案有两类：
+<math display="block">x\equiv45\text{ 或 }95\pmod{100}.</math>
-一般有解时，原模数下恰有 <math>d</math> 个解类。一个模 <math>m/d</math> 的解类，在零到 <math>m-1</math> 中恰好出现 <math>d</math> 次，每次相差 <math>m/d</math>。例如 <math>2x\equiv2\pmod6</math> 等价于 <math>x\equiv1\pmod3</math>，因此解类为一与四；若只写模六等于一，就错误地漏掉了一类。
+代回后 <math>14\cdot45=630</math>，<math>14\cdot95=1330</math>，都余 30。两个解类的出现来自约化后的周期是 50，而原来按 100 分组，一个周期内包含两次这样的解。
-== 用重复平方计算大指数 ==
-同余运算允许每一步都把中间结果缩小，因此大指数不必先形成一个巨大整数。计算 <math>7^{100}\pmod{13}</math>，逐次平方：
-<math display="block">7^2\equiv10,\qquad7^4\equiv10^2\equiv9,\qquad7^8\equiv9^2\equiv3\pmod{13}.</math>
-由 <math>7^{12}=7^8\,7^4</math> 得余数 <math>3\cdot9=27\equiv1</math>。因为一百等于十二乘八再加四，
-<math display="block">7^{100}=(7^{12})^8\,7^4\equiv9\pmod{13}.</math>
-每个简化都由乘法保持同余保证，没有依赖预先计算完整的幂。
-也可以直接把指数写成二进制，按照连续平方得到的幂选择相乘。这是重复平方法的算法结构：平方次数随指数的位数增长，而不是随指数本身逐次相乘。这里的效率说明应与整数乘法本身的成本区分，但已经解释了为何指数很大时仍可能快速求余。
-不能任意把指数也对原模数取余。对于固定底数，幂的周期受可逆性和模数结构控制；它通常不是模数本身。费马小定理在素数模数且底数不被该素数整除时给出周期因子 <math>p-1</math>，欧拉定理则在互素条件下给出更一般的周期因子。没有检查前提便缩减指数，会得到不正确结果。
-== 多个余数怎样确定同一个整数 ==
-求一个整数，使其除以三余二、除以五余三、除以七余二。先从第二个条件写 <math>x=3+5t</math>。模三时变成 <math>2t\equiv2</math>，所以 <math>t=1+3s</math>，得到 <math>x=8+15s</math>。再对七取模，得到 <math>1+s\equiv2</math>，所以 <math>s=1+7k</math>，最终
-<math display="block">x=23+105k,\qquad k\in\mathbb Z.</math>
-二十三分别除以三、五、七，余数是二、三、二；每增加一百零五，三个余数都保持不变。这个答案描述全部整数解，而不是只给最小正解。
-中国剩余定理的一种形式说：若若干正模数两两互素，则任意指定的一组余数，都有唯一的模这些模数之积的解类。唯一性很好理解：两解之差被每个模数整除；模数两两互素，差便被它们的积整除。存在性可以利用裴蜀等式构造在一个模数下为一、在其他模数下为零的数，再按余数加权相加。
+一般方程 <math>ax\equiv b\pmod m</math> 等价于某个整数方程 <math>ax+my=b</math>，因此有解当且仅当 <math>d=\gcd(a,m)</math> 整除 b。有解时，除以 d 后在模 <math>m/d</math> 下得到一个解类，在原模数 m 下则得到 d 个解类。例如把本题右端换成 31，由于 2 不整除 31，方程便无解。
-对两个互素模数 <math>m,n</math>，取 <math>um+vn=1</math>。若要求 <math>x\equiv a\pmod m</math>、<math>x\equiv b\pmod n</math>，构造 <math>x=avn+bum</math> 即可。模 <math>m</math> 时第二项消失、第一项变成 <math>a</math>；模 <math>n</math> 时反过来。这样存在与唯一都有证明，多个模数则可逐步合并。
+== 三条余数信息怎样合成 ==
+《孙子算经》中的一个问题问：一个数除以 3 余 2，除以 5 余 3，除以 7 余 2，它可以是多少？
-模数不互素时，解可能不存在。要求模四余一、模六余二就不可能，因为前者要求奇数，后者要求偶数。一般两个模数的相容条件是它们最大公因数整除两余数之差；相容时解类按最小公倍数确定，而不是机械地按两模数之积确定。额外共享的因数意味着两条余数信息可能重复，也可能冲突。
+先使用除以 5 的条件，写成 <math>x=3+5t</math>。再代入除以 3 的条件，因为 <math>3+5t\equiv2t\pmod3</math>，得到 <math>2t\equiv2\pmod3</math>，所以 <math>t=1+3s</math>。代回得
+<math display="block">x=3+5(1+3s)=8+15s.</math>
+这样表达式已经同时满足前两条条件。最后对 7 取余：
+<math display="block">8+15s\equiv1+s\equiv2\pmod7,</math>
+故 <math>s=1+7k</math>，得到
+<math display="block">x=8+15(1+7k)=23+105k,\qquad k\in\mathbb Z.</math>
+满足三条条件；每增加 <math>105=3\cdot5\cdot7</math>，三个余数都不变。若要求最小正数，答案是 23；若没有大小范围，便有上述无限多个整数解。
-== 整除判据与误差检测的解释 ==
+'''中国剩余定理'''把这个现象推广：若若干模数两两互素，则任意指定的一组余数都能同时实现，而且全部解恰好构成模这些模数之积的一个解类。
-十进制非负整数各位的权重是一、十、一百等。因为 <math>10\equiv1\pmod9</math>，任意十的非负整数幂都模九同余于一，所以一个非负整数与其各位数字之和模九同余。这就是数字和判定九的倍数的理由；对三同理。规则不是十进制数字外观的偶然巧合，而是位值权重在指定模数下的简化。
-例如四万五千七百二十八的数字和为二十六，模九余八，所以原整数也余八，不能被九整除。若检查一次加法运算，可以比较两边模九的余数；不一致必有错误，一致却不能保证正确，因为相差九的倍数的错误完全无法发现。同余校验舍去了信息，因此只可能在一定范围内发现错误，不能恢复全部原始计算。
+=== 两个模数时的构造证明 ===
+设 m、n 互素，要求 <math>x\equiv a\pmod m</math>、<math>x\equiv b\pmod n</math>。裴蜀等式提供 <math>um+vn=1</math>。其中 vn 模 m 余 1、模 n 余 0；um 恰好相反。于是取
+<math display="block">x=avn+bum.</math>
+模 m 时，第二项为零，第一项为 a；模 n 时，第一项为零，第二项为 b。这证明解存在。
-类似地，因 <math>10\equiv-1\pmod{11}</math>，十进制非负整数与各位交错和模十一同余。对于一万二千三百二十一，从个位开始交错求和得到 <math>1-2+3-2+1=1</math>，所以不能被十一整除。对于负整数，应先对绝对值计算数字和或交错和，再附上原数的负号；例如负十二模九余六，而其绝对值的数字和为三。这里起始符号选反只会整体变号，不影响判断余数是否为零，但若要精确报告余数则必须保持一致。
+若 x、x′ 都是解，其差同时被 m、n 整除。写 <math>x-x'=mr</math>，由 n 与 m 互素，<math>n\mid mr</math> 推出 <math>n\mid r</math>，所以 <math>mn\mid(x-x')</math>。反过来，给一个解加上 mn 的任意倍数，两个余数都不变。这就证明全部解正好相差 mn 的倍数。多个两两互素的模数，可以逐步合并。
-在有限剩余类中，加法总有逆元，因此形成循环群；乘法却只有与模数互素的类才有逆元。当模数为素数时，全体剩余类在加法、乘法下构成有限域；非零剩余类在乘法下构成群。合数模数下可能出现两个非零类相乘为零，例如模六的二与三。这个边界把同余计算连接到[[群]]与一般代数，也解释为什么“除以非零数”仍可能非法。
+模数有共同因子时，要求可能冲突。例如模 4 余 1 要求 x 为奇数，模 6 余 2 却要求 x 为偶数，因而无解。一般两个模数的条件相容，当且仅当它们的最大公因数整除两余数之差。相容时，解的周期为两模数的最小公倍数，共同因子所包含的信息只计一次。
-=== 何时能从余数恢复原来的数 ===
+== 为什么数字和能判断整除 ==
-一条同余式只给出一个无限等差数列；若再知道整数处于一个长度小于模数的范围内，就至多有一个候选。例如已知某整数模一百零五余二十三，并且在零到一百之间，只能是二十三；若范围改为零到二百，就可能是二十三或一百二十八。余数与范围是两种不同信息，组合起来才可能恢复原值。
+一个十进制非负整数由各位数字乘上相应位值组成。例如
+<math display="block">45728=4\cdot10^4+5\cdot10^3+7\cdot10^2+2\cdot10+8.</math>
+由于 <math>10\equiv1\pmod9</math>，每个十的非负整数次幂都模 9 余 1。因此
+<math display="block">45728\equiv4+5+7+2+8=26\equiv8\pmod9.</math>
+所以 45728 不能被 9 整除。对任何十进制非负整数，同样的逐项化简都成立，便得到“数字和能被 9 整除，原数也能被 9 整除”的判据。模 3 时也有 <math>10\equiv1</math>，理由相同。
-多个互素模数提供更多区分能力，因为它们合并后的有效模数是乘积。但这不表示余数数量越多就必然增加同样多的信息：模四与模二的条件有重叠，知道模四的余数就已经知道奇偶性。非互素的中国剩余问题需要最小公倍数，正是因为共享因子重复记录了部分周期信息。
+模 11 时则有 <math>10\equiv-1</math>，所以从个位起，位值的余数依次是 1、−1、1、−1……。例如
+<math display="block">12321\equiv1-2+3-2+1=1\pmod{11},</math>
+故它不能被 11 整除。起始符号取反会使整个结果变号，不影响是否为零，但会改变所报告的具体余数。
-在推导整数恒等式时，证明两边模某个数同余，通常还不足以证明两边相等。若能同时证明两边之差的绝对值严格小于模数，才可结合“差是模数倍数”推出差为零。这是把粗略的余数信息升级为精确等式的一种常见方法，也说明范围估计有时与代数计算同样重要。
+对负整数，可先处理其绝对值，再加上负号。例如 12 的数字和是 3，但 <math>-12\equiv-3\equiv6\pmod9</math>，余数不是 3。
-同余式也不能直接比较代表数的大小。例如模五的四也可用负一表示，若把某种大小顺序视为剩余类本身的性质，两种代表会给出不同结论。剩余类自然继承加法和乘法，却没有自动继承整数的通常大小次序。计算时选用较小代表只是方便，不是发现了该类别唯一的真实大小。
+同余还能用于检查运算。若一个加法等式两边模 9 的结果不同，等式一定错了；结果相同，则仍可能相差 9、18 等倍数。校验保留了余数，却没有保留完整数值。若另外已知两边之差的绝对值小于 9，“差是 9 的倍数”才会迫使差为零。
-== 从古代余数问题到高斯的系统语言 ==
+== 余数类与信息的范围 ==
-《孙子算经》包含按三、五、七计数所得余数反求总数的问题，正是上面二十三的算例来源。其成书年代存在研究争议，作者生平资料也很有限，不宜编造精确发现年份，或把数学家孙子与兵家孙武混同。[https://mathshistory.st-andrews.ac.uk/Biographies/Sun_Zi/ MacTutor：Sun Zi]讨论了文本、问题与年代判断。
+所有模 m 与 a 同余的整数组成一个'''剩余类'''：
+<math display="block">[a]_m=\{a+km:k\in\mathbb Z\}.</math>
+例如模 5 的零类是全部 5 的倍数。模 5 共有五个不同的类，可以用 0、1、2、3、4 代表；每个类却含有无限多个整数。
-Gauss 在 1801 年出版《算术研究》，以同余为组织整数论的重要语言。古代余数问题、后来的构造方法与高斯的统一表述，是不同层次的贡献；因此不能说余数思想到十九世纪才出现。[https://www.loc.gov/item/36021572/ 美国国会图书馆的 1801 年《Disquisitiones arithmeticae》书目]核对出版信息，[https://mathshistory.st-andrews.ac.uk/DSB/Gauss.pdf Gauss 的学术传记]说明同余概念在书中的作用。
+同余具有自反性、对称性和传递性，分别来自 <math>a-a=0</math>、<math>b-a=-(a-b)</math> 和 <math>a-c=(a-b)+(b-c)</math>。因此它是一种[[集合|等价关系]]。两类若有共同元素，就可以通过这个元素推出两位代表同余，因而两类完全相同；否则它们不相交。这样，全部整数被整齐分为 m 类。
-== English overview ==
+类的加法和乘法可以由代表数计算，因为前面已经证明更换同余代表不影响结果。模 6 时，非零的 2 类与 3 类相乘却为零类，这也解释了为什么非零代表不一定有乘法逆元。剩余类在加法下形成循环[[群]]，模逆元则挑出哪些类能够进行可逆的乘法。
-<div lang="en" class="math-english-summary">
-Two integers are congruent modulo a positive integer m when their difference is divisible by m. Congruence retains a remainder class while discarding full magnitude information. It is an equivalence relation, and its classes partition the integers.
-Addition, subtraction, multiplication, and nonnegative integer powers respect congruence. Division requires special care: a multiplier can be cancelled without changing the modulus only when it is coprime to that modulus. Modular inverses exist exactly under this coprimality condition. A linear congruence ax = b modulo m is solvable precisely when gcd(a,m) divides b; when solvable, it has that many solution classes modulo m.
+余数信息有时可以配合范围确定原数。例如已经得到 <math>x\equiv23\pmod{105}</math>，再知道 <math>0\le x\le100</math>，便只有 23 一个候选；若范围是 0 到 200，则还有 128。选择 23 或 −82 作为代表都表示同一类，代表的大小并不是整个剩余类的内在大小。
-Worked examples solve a congruence with two solution classes, evaluate a large power, and combine three remainder conditions. The Chinese remainder theorem gives existence and uniqueness modulo the product for pairwise coprime moduli. Noncoprime moduli require compatibility checks. Digit tests and modular error checks illustrate what remainder information can detect and what it necessarily loses. Historical discussion distinguishes early remainder problems in the Sunzi text from Gauss's systematic nineteenth century treatment.
+== 历史 ==
-</div>
+《孙子算经》记载了上面的三、五、七余数问题。文本的成书年代及作者生平仍有不确定之处；[https://mathshistory.st-andrews.ac.uk/Biographies/Sun_Zi/ MacTutor：Sun Zi]整理了相关文献与年代判断。
-== 编者评注（AI 辅助） ==
+Gauss 在 1801 年出版《算术研究》，把同余作为系统组织整数论的重要语言。书目可见 [https://www.loc.gov/item/36021572/ 美国国会图书馆的原书记录]；[https://mathshistory.st-andrews.ac.uk/DSB/Gauss.pdf Gauss 的学术传记]说明了这种表述在书中的作用。从按组计数反求总数，到用统一符号处理整除、幂与方程，余数问题逐渐形成了系统理论。
-本条把“哪些运算保留同余”作为主线，尤其解释约去因子时为什么有时必须同时改变模数。线性方程的两类解与非互素余数条件都是容易遗漏的边界；算例先给全部解，再核验代表值。内容由 AI 辅助整理；编者认为钟面比喻只适合作为入口，必须继续说明信息损失、等价类与逆元条件，才能避免把模运算误当成普通等式的简写。
-== 参考资料与后续阅读 ==
+== 参考资料 ==
-* [https://twjudson.github.io/aata-files/aata-html/aata-toc.html Thomas W. Judson，Abstract Algebra: Theory and Applications]：整数、剩余类和循环群的开放教材。
+* [https://twjudson.github.io/aata-files/aata-html/aata-toc.html Thomas W. Judson，Abstract Algebra: Theory and Applications]：整数与剩余类。
 * [https://math.gordon.edu/ntic/ntic/ntic.html Karl-Dieter Crisman，Number Theory: In Context and Interactive]：同余、模幂和中国剩余定理。
-* [https://mathshistory.st-andrews.ac.uk/Biographies/Sun_Zi/ J. J. O’Connor、E. F. Robertson，Sun Zi]：古代余数问题与史料边界。
+* [https://mathshistory.st-andrews.ac.uk/Biographies/Sun_Zi/ J. J. O’Connor、E. F. Robertson，Sun Zi]。
-* [https://www.loc.gov/item/36021572/ Library of Congress，Disquisitiones arithmeticae，1801]：Gauss 原著书目。
+* [https://www.loc.gov/item/36021572/ Library of Congress，Disquisitiones arithmeticae，1801]。
-* 前置可读[[整数整除]]、[[素数]]；继续阅读[[群]]、[[集合]]和[[逻辑]]。
+* 相关条目：[[整数整除]]、[[素数]]、[[集合]]、[[群]]、[[逻辑]]。
 [[分类:数论]]