中国剩余定理

破除误解#

第二条要拆开的，是发明权，以及「只是一道古代趣题」。高斯不是这条定理的发明人。他在 1801 年的《算术研究》（Disquisitiones Arithmeticae）里用同余把一次剩余写成系统的条目。同余这个写法是在这本书里立起来的。按几个模同时求剩余，书里是在整理，不是在宣布这件事从这一年才成立。卷下那一问更早，而且它只处理三、五、七这一个互素的例子，外加这组模上任意余数怎么拼。例子是装置。定理说的是：只要模两两互素，任意余数都有解，解在模乘积下唯一。把定理收成趣题，会把「任意余数」和「模乘积」一起删掉。趣题负责让人看见二十三。定理负责说明为什么余数可以换成别的，以及为什么模不能随便换成不互素的一组。

第三条要拆开的，是快速傅里叶变换。环在模数合适时可以拆成直积，计算机上的快速乘法用得到这种分裂。那是同一条同构的另一面，不是本页要教的变换。本页不写代码，不画蝶形，也不把运算次数写成结论。变换那一页的未知数，是一组样本如何换成频谱。本页的未知数，是一个整数如何同时满足几条剩余。速度是算法页的账。有没有解、解在哪个模下只剩一类，才是这里的账。

第四条要拆开的，是模数不互素时仍假装总有唯一解。三、五、七两两互素，乘积一百零五就是最小公倍数，趣题看不出裂痕。换成别的模，存在和唯一会分开。$x \equiv 1 \pmod{2}$ 并且 $x \equiv 2 \pmod{4}$，没有整数解。凡是被四除余二的数，被二除也余二，不会余一。$x \equiv 2 \pmod{4}$ 并且 $x \equiv 4 \pmod{6}$，解是有的，十和二十二都满足，相差十二。十二是四和六的最小公倍数。四乘六得二十四，十和二十二在模二十四下并不是同一个类。互素是前提，不是可以省略的礼貌。

定理在说什么#

把这一问写成同余，就是三条式子同时成立。$x \equiv 2 \pmod{3}$，$x \equiv 3 \pmod{5}$，$x \equiv 2 \pmod{7}$。一般地，给定正整数模 $m_1,\ldots,m_k$ 和任意整数余数 $a_1,\ldots,a_k$，要找的是所有这样的 $x$：对每个 $i$，都有 $x \equiv a_i \pmod{m_i}$。也就是 $m_i$ 整除 $x-a_i$。未知数仍是这一个 $x$，不是那些模，也不是那些余数。

经典陈述只锁两两互素的情形。若 $i \neq j$ 时 $\gcd(m_i,m_j)=1$，则上面的组必有整数解。任意两个解相差 $M = m_1 \cdots m_k$ 的倍数。换句话说，解在模 $M$ 下恰好一个类。余数可以随便指定。存在性不靠余数之间再凑条件。三、五、七满足前提，所以二、三、二这组余数有解，而且模一百零五只有一类。二十三是这一类里落在零与一百零四之间的那个非负代表。

下面这条和式就是解的一种写法，前提是模已经两两互素。令 $M_i = M / m_i$。因为别的模都与 $m_i$ 互素，$M_i$ 也与 $m_i$ 互素，所以存在整数 $y_i$，使 $M_i y_i \equiv 1 \pmod{m_i}$。取

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

第 $i$ 项在模 $m_i$ 下等于 $a_i$，因为 $M_i y_i$ 余一，再乘 $a_i$ 就余 $a_i$。同一项被其余每个 $m_j$ 整除，因为 $M_i$ 已经包含那些因子。于是和式在每条模下只留下自己的那一项。这就是解。卷下没有写这套字母。它直接给出这组模的成品。七十被五和七整除，被三除余一。二十一被三和七整除，被五除余一。十五被三和五整除，被七除余一。余数二、三、二上去，就是 $2 \times 70 + 3 \times 21 + 2 \times 15 = 233$。再减去两个一百零五，得到二十三。和式里的 $y_i$，对三、五、七来说就是二、一、一，因为 $35 \times 2 = 70$。求这种逆元，用的是互素时一次不定方程有解。高斯写明，这类方程的一般解法先由 欧拉 发表。本页不转写他标注的卷页，也不把辗转相除的算草列成步骤。

唯一性不靠再造一个和式。设 $x$ 与 $x'$ 都满足全部同余，则每个 $m_i$ 都整除 $x-x'$。模两两互素时，乘积 $M$ 也整除 $x-x'$。两条模先看清楚：若 $\gcd(m,n)=1$，$m$ 与 $n$ 都整除 $k$，则 $mn$ 整除 $k$。多条是同一句话反复用。这件事比同余符号老。欧几里得 整理过的算术里，素数整除乘积就必须整除其中一个因子；互素整数的这条连乘，是同一传统里的下一步。高斯在写联立同余之前，先把「互素的一组数都整除 $k$，则乘积整除 $k$」记在同余的初步性质里。本页借的是这一步。不是说《几何原本》里已经有「物不知数」。

因此「有解」和「只有一个整数」不是一回事。定理保证的是模 $M$ 的一个剩余类。类里有无穷个整数，正的、负的、比 $M$ 大的都算。$-82 = 23 - 105$，被三除余二，被五除余三，被七除余二。书上答二十三，是因为问的是物数，取了非负而且小于模的那个。若把答数读成「世界上只有二十三这一个整数满足三句话」，定理就被说窄了，术文里的「减之」也失去作用。

历史要分三层，不要焊成一个人。卷下给出的是固定模三、五、七，以及这组模上按余数拼解、再减去一百零五的办法。它没有对任意一组模陈述定理，也没有写「模乘积唯一」这句现代话。南宋秦九韶在淳祐七年，即 1247 年，写成后世通称的《数书九章》。这部书也以《数术大略》为名。书首大衍类处理一次同余组。问数不必两两互素，也可以先从小数、分数化到整数。整套算法他称为大衍总数术。其中求乘率的一步才叫大衍求一术。这里的「奇数」不是奇偶，而是衍数被定母去除剩下的数。乘率乘它，被定母除余一。不互素的问数要先用「两两连环求等」收成两两互素的定母，求一才用得上。所以求一不是不互素情形的全部，而是化完以后的那一步。这是对卷下那一问的推广。推广的对象是模可以更一般，不是把二十三再算一遍。

欧洲近代的系统叙述在高斯，不在卷下的出生证明里。《算术研究》第二卷讨论一次同余。从书自身的第 32 条起，问题是：按若干给定的模，求与给定剩余同余的数。第 33 条写明，模彼此互素时，整组等价于模乘积下的一条同余。第 36 条在互素的前提下，用各模的「余一且被其余模整除」的倍数把解拼出来，就是上面的和式。这些是书里的条目号，不是后人另编的定理号。第 32 条也处理模不互素的情形：先把两条收成一条，模取最小公倍数；若这一步的一次同余无解，整组就无解。有第三条，就用同一办法再并一次。这是整理，不是发明。二次互反在同一本书的后部，问的是平方剩余，不是这条公共剩余。

不互素时，存在要另写，而且本页只把充要条件写到能核对的程度。两条同余 $x \equiv a \pmod{m}$ 与 $x \equiv b \pmod{n}$ 有解，当且仅当 $a-b$ 被 $\gcd(m,n)$ 整除。有解时，解在模 $\operatorname{lcm}(m,n)$ 下唯一，不一定在模 $mn$ 下唯一。前面的两组数可以当场检验。一减二得负一，二不整除负一，所以模二余一与模四余二无解。二减四得负二，二整除负二，所以模四余二与模六余四有解，唯一性的模是十二，不是二十四。多条时，只要有一对的余数差不能被那一对的最大公因数整除，整组必无解。反过来，每一对都满足时，整组有解，解在全体模的最小公倍数下唯一。高斯的写法是把已解的部分收成一条，再与下一条合并。合并的手续，以及秦九韶把问数收成定母的筹算，本页都不逐步展开。

它保证什么，不保证什么#

它保证的只有这一件。模两两互素时，余数可以任意指定，同余组必有解，全部解合成模乘积的一个类。和式给出类里的一个代表。整除引理把其余的解都锁进同一个类。二十三、一百二十八和负八十二是这个类上的三个点。小于模的非负代表只是写法。试到二十三，只解决三、五、七上的这一组余数。七十、二十一、十五也只服务这组模。定理给的是换模以后仍然成立的理由。

它不保证模不互素时仍有解，也不保证那时解在乘积下唯一。无解，以及有解但模二十四下分成两类，上面都已摆出。不互素而仍然有解时，唯一性的模是最小公倍数。乘积只在两两互素时才和最小公倍数重合。

它不分解整数。算术基本定理回答素数幂怎么写。本定理回答一组剩余能不能粘成一个类。旅馆那一页用素数幂避免撞房，用的是前一条。因子从哪来，不是剩余类的唯一性给的。

它不算变换的步数。模多项式拆成两两互素的因子时，商环可以拆成直积。重因子不能假装成互素的一次块。样本怎么分、乘法次数怎么降，写在变换那一页。未知数仍是剩余类。

它也不为实现上的加速背书。RSA 公钥密码那一页把模两个素数之积的私钥幂拆开再合并。合并后类唯一，是因为不同素数互素。那一页说大约快到四倍，是实现之间的比较。倍数、填充和分解的难度都不从本定理推出来。

环的说法是同一件事。把模 $M$ 的类送到 $(x \bmod m_1,\ldots,x \bmod m_k)$。加法和乘法都按分量走。两两互素时这是环同构，每个剩余组恰好一个来源。不互素时同态还在，一一对应没有了。有的组没有来源，有的来源不止一个。环那一页说在某些条件下可以分解为直积。对整数商环，条件就是这些模两两互素。这修不好理想论里另一种拆不开，也不是任何商环都会自动裂开。

跨域连接#

• 数论：数论页把同余和素因子分解并列，又用一句话记下本定理在两两互素时的结论。同余把整数收成有限个类。分解把乘法拆成素数幂。本页只展开联立剩余：未知数是同时满足几条剩余的那个整数，唯一性只活在模乘积的一个类里。不要把「模 $n$ 的幂可以分而治之」读成本定理会输出素因子。类能够粘合，因子仍要另算。欧拉定理、二次互反和素数有多少，问的也不是这一个未知数。
• 环：环页把这条定理写成直积。在某些条件下，一个环拆成更小的环的乘积。整数商环上可以写死：模两两互素，则模乘积的剩余环同构于各模剩余环的直积。有解且解类唯一，就是这个同构在元素上的样子。环页更关心理想，以及唯一分解何时失败。同一个数写成两种互不相当的积，那是另一种拆不开，不是同余组无解。两边都说拆开，拆开的东西不同。
• 欧几里得：模乘积下的唯一，靠的不是同余号，而是互素的除数可以连乘。一对数互素，而且每一个都整除同一个整数，则乘积也整除它。多条模是这句话再走几步。欧几里得页整理的是从公设推出几何，以及素数有无穷多个。《几何原本》没有「物不知数」，也没有后来的同余符号。本页借的是整除引理所在的算术，不把发明权送回亚历山大。高斯写联立同余之前先记下这条引理。引理是工具，不是趣题的别名。
• 快速傅里叶变换：环页说，模多项式若能完全分裂，商环就同构于许多小环的直积，大乘法拆成小乘法，并把这一面与中国剩余定理看成同一条定理。快速傅里叶变换那一页的对象是离散样本和频谱，蝶形和运算次数都写在那里。本页不重复那些步骤。能这么拆，仍是因为因子两两互素。重因子不能照抄直积。不要把变换的速度写成这条同余定理的结论，也不要把二十三写成一套频谱算法。
• 高斯：人物页上的关键著作就是《算术研究》。1801 年这本书用同余把一次剩余系统化，联立同余在第二卷，条目 32 至 36。两两互素时，整组收成模乘积下的一条。不互素时，他按最小公倍数合并，某一步无解则整组无解。这是欧洲近代的系统叙述。卷下的问，以及 1247 年的大衍类，都早于这本书。不要把「奠定数论」读成「同余组从这一年才有解」。同余符号是新的。公共剩余不是新的。二次互反是同一本书的另一条主线，不能并进剩余类的唯一性。

参考文献#

1. 佚名，《孙子算经》卷下「物不知数」。整理本：钱宝琮校点，《算经十书》，中华书局，1963。
2. 秦九韶，《数书九章》（亦题《数术大略》），淳祐七年（1247），大衍类。大衍总数术处理一次同余组，大衍求一术是其中求乘率的一步。
3. Carl Friedrich Gauss, Disquisitiones Arithmeticae, 1801。联立同余见第二卷条目 32–36。条目号是原书的，不是另编的定理号。

延伸阅读#

• 与 数论、环 对读：一页把同余和素因子分解并列，一页把互素模之下的同构写成直积。不要并成一句「整数总能拆开」。
• 与 高斯、欧几里得 对读：1801 年的同余条目怎样使用更早的整除引理，而不把引理或那一年写成这条定理的诞生。
• 与 快速傅里叶变换 对读：用分裂少做乘法的那一面留在算法页。本页停在剩余类有没有解、解在哪个模下唯一。
• 华罗庚《从孙子的「神奇妙算」谈起》用这道题引出同余。那是读物，不是卷下的校勘本。人物页见 华罗庚。