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

'''同余'''（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> 后余数相同。同余保留与某种周期有关的信息，舍去完整整数的大小信息，是[[整数整除]]、周期计算和代数结构之间的桥梁。

== 钟面留下了哪些信息 ==
十二小时钟面上，十五时与三时指向相同刻度，因为两者相差十二；增加二十四小时也不改变刻度。这个比较不表示十五与三作为整数相等，而是说在“只关心十二小时周期位置”的问题中，它们无法区分。模数说明当前舍去了哪一部分信息，不能在计算中无声更换。

同样，<math>17\equiv5\pmod{12}</math>，而 <math>-1\equiv11\pmod{12}</math>。负数并没有特殊障碍，因为差仍可被模数整除。使用代表数时常选零到 <math>m-1</math>，但任何同余整数都可代表同一类别；为了心算方便，把十一写成负一有时更简洁。

“取模得到余数”是一种产生代表数的操作，“同余”则是两个整数之间的关系。例如 <math>17\bmod12=5</math> 表示所选非负余数，而同余式可写成 <math>17\equiv-7\pmod{12}</math>，右侧不必是标准余数。程序语言对负数取余的约定可能不同，不能据此改变数学同余关系本身。

模数一也可以定义，此时所有整数同余，只有一个剩余类；本条主要采用 <math>m\ge2</math>，以保留非平凡的区分。模数零不按普通余数运算处理。明确这些边界，可以避免把定义式中的整除和常见程序操作直接混为一谈。

== 剩余类把整数分成互不重叠的类别 ==
模 <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>a\equiv a'\pmod m</math>、<math>b\equiv b'\pmod m</math>，则加法、减法和乘法都保持同余。加减法的理由是两组差仍为模数倍数；乘法则利用
<math display="block">ab-a'b'=(a-a')b+a'(b-b').</math>
右侧每项都含有一个被模数整除的因子，因此总差也被整除。这证明可以在计算中随时把整数换成较小的同余代表，而不会改变最终余数。

非负整数次幂与整系数多项式也保持同余，因为它们由有限次加法和乘法构成。必须保留“整系数”或另行解释分母可逆性，不能把带除法的任意表达式直接代入。平方根也不能直接保持唯一性，因为不同剩余类可能有相同平方。

例如 <math>2\cdot1\equiv2\cdot4\pmod6</math>，但一与四模六不同余，所以不能简单约去二。问题在于二与六共享因数，乘二后可能把不同类别合并。这与实数中乘非零数不会合并输入的情形不同。把普通等式消去规则原封不动搬来，会丢掉合法解。

正确的消去结论是：若 <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>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>50=7\cdot7+1</math>，整理为 <math>1=50-7\cdot7</math>，所以七模五十的逆元是负七，也可用四十三代表。验证 <math>7\cdot43=301\equiv1\pmod{50}</math>。求逆元是在特定模数下撤销乘法，不是普通分数 <math>1/7</math> 的十进制近似。

线性同余方程 <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>，就得到系数与新模数互素的方程，能够通过逆元求解。

完整计算 <math>14x\equiv30\pmod{100}</math>。最大公因数为二，确实整除三十，约化后得到 <math>7x\equiv15\pmod{50}</math>。乘以逆元四十三，
<math display="block">x\equiv43\cdot15=645\equiv45\pmod{50}.</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>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>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> 时反过来。这样存在与唯一都有证明，多个模数则可逐步合并。

模数不互素时，解可能不存在。要求模四余一、模六余二就不可能，因为前者要求奇数，后者要求偶数。一般两个模数的相容条件是它们最大公因数整除两余数之差；相容时解类按最小公倍数确定，而不是机械地按两模数之积确定。额外共享的因数意味着两条余数信息可能重复，也可能冲突。

== 整除判据与误差检测的解释 ==
十进制非负整数各位的权重是一、十、一百等。因为 <math>10\equiv1\pmod9</math>，任意十的非负整数幂都模九同余于一，所以一个非负整数与其各位数字之和模九同余。这就是数字和判定九的倍数的理由；对三同理。规则不是十进制数字外观的偶然巧合，而是位值权重在指定模数下的简化。

例如四万五千七百二十八的数字和为二十六，模九余八，所以原整数也余八，不能被九整除。若检查一次加法运算，可以比较两边模九的余数；不一致必有错误，一致却不能保证正确，因为相差九的倍数的错误完全无法发现。同余校验舍去了信息，因此只可能在一定范围内发现错误，不能恢复全部原始计算。

类似地，因 <math>10\equiv-1\pmod{11}</math>，十进制非负整数与各位交错和模十一同余。对于一万二千三百二十一，从个位开始交错求和得到 <math>1-2+3-2+1=1</math>，所以不能被十一整除。对于负整数，应先对绝对值计算数字和或交错和，再附上原数的负号；例如负十二模九余六，而其绝对值的数字和为三。这里起始符号选反只会整体变号，不影响判断余数是否为零，但若要精确报告余数则必须保持一致。

在有限剩余类中，加法总有逆元，因此形成循环群；乘法却只有与模数互素的类才有逆元。当模数为素数时，全体剩余类在加法、乘法下构成有限域；非零剩余类在乘法下构成群。合数模数下可能出现两个非零类相乘为零，例如模六的二与三。这个边界把同余计算连接到[[群]]与一般代数，也解释为什么“除以非零数”仍可能非法。

=== 何时能从余数恢复原来的数 ===
一条同余式只给出一个无限等差数列；若再知道整数处于一个长度小于模数的范围内，就至多有一个候选。例如已知某整数模一百零五余二十三，并且在零到一百之间，只能是二十三；若范围改为零到二百，就可能是二十三或一百二十八。余数与范围是两种不同信息，组合起来才可能恢复原值。

多个互素模数提供更多区分能力，因为它们合并后的有效模数是乘积。但这不表示余数数量越多就必然增加同样多的信息：模四与模二的条件有重叠，知道模四的余数就已经知道奇偶性。非互素的中国剩余问题需要最小公倍数，正是因为共享因子重复记录了部分周期信息。

在推导整数恒等式时，证明两边模某个数同余，通常还不足以证明两边相等。若能同时证明两边之差的绝对值严格小于模数，才可结合“差是模数倍数”推出差为零。这是把粗略的余数信息升级为精确等式的一种常见方法，也说明范围估计有时与代数计算同样重要。

同余式也不能直接比较代表数的大小。例如模五的四也可用负一表示，若把某种大小顺序视为剩余类本身的性质，两种代表会给出不同结论。剩余类自然继承加法和乘法，却没有自动继承整数的通常大小次序。计算时选用较小代表只是方便，不是发现了该类别唯一的真实大小。

== 从古代余数问题到高斯的系统语言 ==
《孙子算经》包含按三、五、七计数所得余数反求总数的问题，正是上面二十三的算例来源。其成书年代存在研究争议，作者生平资料也很有限，不宜编造精确发现年份，或把数学家孙子与兵家孙武混同。[https://mathshistory.st-andrews.ac.uk/Biographies/Sun_Zi/ MacTutor：Sun Zi]讨论了文本、问题与年代判断。

Gauss 在 1801 年出版《算术研究》，以同余为组织整数论的重要语言。古代余数问题、后来的构造方法与高斯的统一表述，是不同层次的贡献；因此不能说余数思想到十九世纪才出现。[https://www.loc.gov/item/36021572/ 美国国会图书馆的 1801 年《Disquisitiones arithmeticae》书目]核对出版信息，[https://mathshistory.st-andrews.ac.uk/DSB/Gauss.pdf Gauss 的学术传记]说明同余概念在书中的作用。

== English overview ==
<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.

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>

== 编者评注（AI 辅助） ==
本条把“哪些运算保留同余”作为主线，尤其解释约去因子时为什么有时必须同时改变模数。线性方程的两类解与非互素余数条件都是容易遗漏的边界；算例先给全部解，再核验代表值。内容由 AI 辅助整理；编者认为钟面比喻只适合作为入口，必须继续说明信息损失、等价类与逆元条件，才能避免把模运算误当成普通等式的简写。

== 参考资料与后续阅读 ==
* [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]：Gauss 原著书目。
* 前置可读[[整数整除]]、[[素数]]；继续阅读[[群]]、[[集合]]和[[逻辑]]。
[[分类:数论]]