查看“︁同余”︁的源代码

'''同余'''（congruence）用来表示两个整数除以同一个正整数时余数相同。例如 17 和 5 除以 12 都余 5，记作 <math>17\equiv5\pmod{12}</math>，读作“17 与 5 模 12 同余”。这里的 12 称为'''模数'''。

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

== 相同余数，就是相差整倍数 ==
设整数 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>-1\equiv11\pmod{12}</math>，因为二者相差 −12。余数通常选在 <math>0,1,\ldots,m-1</math> 中，但同余式右边可以使用其他代表，如 <math>17\equiv-7\pmod{12}</math>。这类似于从钟面 12 点往前退一格，可以用 −1 表示，也可以用 11 表示。

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

[[File:Gezhi-teaching-foundation-congruence-clock.svg|frame|center|alt=两个模十二钟面，左图顺时针一圈加五格停在五，右图从零逆时针一格停在十一|17 与 5、−1 与 11 各自相差一个完整的 12 格周期。]]

记号 <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 display="block">\begin{aligned}
7^2&=49\equiv10,\\
7^4&\equiv10^2=100\equiv9,\\
7^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 的幂之和，再选择连续平方得到的结果相乘。

== 除法为何需要额外条件 ==
同余中的乘法可能把不同余数合并。例如模 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 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 display="block">au\equiv1\pmod m.</math>
u 叫 a 的'''模逆元'''。两边乘 u，便能撤销乘 a 的作用。

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

== 完整求解一个同余方程 ==
求所有整数 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>
7 与 50 已经互素。由 <math>50=7\cdot7+1</math>，可写 <math>1=50-7\cdot7</math>，所以 7 的逆元是 −7，或等价地用 43 表示。验证有 <math>7\cdot43=301\equiv1\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>14\cdot45=630</math>，<math>14\cdot95=1330</math>，都余 30。两个解类的出现来自约化后的周期是 50，而原来按 100 分组，一个周期内包含两次这样的解。

一般方程 <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，方程便无解。

== 三条余数信息怎样合成 ==
《孙子算经》中的一个问题问：一个数除以 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>
23 满足三条条件；每增加 <math>105=3\cdot5\cdot7</math>，三个余数都不变。若要求最小正数，答案是 23；若没有大小范围，便有上述无限多个整数解。

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

=== 两个模数时的构造证明 ===
设 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。这证明解存在。

若 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 的倍数”才会迫使差为零。

== 余数类与信息的范围 ==
所有模 m 与 a 同余的整数组成一个'''剩余类'''：
<math display="block">[a]_m=\{a+km:k\in\mathbb Z\}.</math>
例如模 5 的零类是全部 5 的倍数。模 5 共有五个不同的类，可以用 0、1、2、3、4 代表；每个类却含有无限多个整数。

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

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

余数信息有时可以配合范围确定原数。例如已经得到 <math>x\equiv23\pmod{105}</math>，再知道 <math>0\le x\le100</math>，便只有 23 一个候选；若范围是 0 到 200，则还有 128。选择 23 或 −82 作为代表都表示同一类，代表的大小并不是整个剩余类的内在大小。

== 历史 ==
《孙子算经》记载了上面的三、五、七余数问题。文本的成书年代及作者生平仍有不确定之处；[https://mathshistory.st-andrews.ac.uk/Biographies/Sun_Zi/ MacTutor：Sun Zi]整理了相关文献与年代判断。

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

== 参考资料 ==
* [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://www.loc.gov/item/36021572/ Library of Congress，Disquisitiones arithmeticae，1801]。
* 相关条目：[[整数整除]]、[[素数]]、[[集合]]、[[群]]、[[逻辑]]。
[[分类:数论]]