中国剩余定理

中国剩余定理
术语名称	中国剩余定理
英语名称	Chinese remainder theorem
别名	CRT, 孙子定理, Sunzi's theorem, 孙子–秦九韶定理

中国剩余定理(Chinese remainder theorem， CRT)或孙子定理、孙子–秦九韶定理，指模数互质的同余方程组的解的一种构造方法。

定理

对一次同余方程组

[math]\displaystyle{ \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \dots \\ x \equiv a_k \pmod {m_k} \end{cases} }[/math]

其中 [math]\displaystyle{ m_1, m_2, \dots, m_k }[/math] 两两互质。

记 [math]\displaystyle{ M = m_1 m_2 \dots m_k }[/math] 及 [math]\displaystyle{ M = m_j M_j }[/math]，且可求模逆得 [math]\displaystyle{ M_j M_j^{-1} \equiv 1 \pmod {m_j} }[/math] ，

则 [math]\displaystyle{ x\equiv \sum_{j=1}^k M_j M_j^{-1} a_j \pmod{M} }[/math] 是其解。

注：前一半的 [math]\displaystyle{ M_j M_j^{-1} \equiv 1 \pmod {m_j} }[/math] 和拉格朗日插值法中拆分的多项式想法是相似的，由于 [math]\displaystyle{ m_i \mid M_j, i\neq j }[/math] ，结果上必然有

[math]\displaystyle{ M_j M_j^{-1} \equiv \begin{cases} 1 \pmod{m_i} &, j=i \\ 0 \pmod{m_i} &, j\neq i \\ \end{cases} }[/math]

中国剩余映射

中国剩余映射
术语名称	中国剩余映射
英语名称	Chinese remainder map

中国剩余定理建立了一系列模数互质的完全剩余系与以模数之积为新的模数的完全剩余系之间的双射，称为中国剩余映射(Chinese remainder map)。

[math]\displaystyle{ f: \mathbb{Z}/m\mathbb{Z} \to (\mathbb{Z}/m_1\mathbb{Z} \times \dots \times \mathbb{Z}/m_k\mathbb{Z}); x\mapsto (x\bmod m_1, \dots, x\bmod m_k) }[/math]

性质

复杂的一次同余方程组总是可以化成多个简单的一次同余方程组，若然后通过中国剩余定理求解。

中国剩余定理过程中最重要的过程是求取模逆的过程，可以通过大衍求一术或其他等价方法完成。

中国剩余定理对任意主理想整环都成立，且这些环上也都存在相当于中国剩余映射的环同构。

同余理论
同余	剩余类	互质剩余类
	完全剩余系	简化剩余系、Euler 函数
	Fermat 小定理	Euler 定理
一元同余方程
一次	一次同余方程、大衍求一术
	中国剩余定理
二次	二次同余方程、二次剩余
	Euler 准则、Legendre 符号、二次互反律、Jacobi 符号
高次	二项同余方程、[math]\displaystyle{ n }[/math] 次剩余
	质数模高次同余方程、Lagrange 定理、等价同余方程

琐事

命名

因为《孙子算经》中只提到了一个具体的模 3、5、7 的同余方程组，“孙子定理”一词有时仅指三个同余方程的情况。

后续由秦九韶整理并推广为大衍总数术，除同余方程数可以扩展到多个，还涉及模数和系数需要先约分等的情况。因此，任意个同余方程的情况也被称为孙子–秦九韶定理。

“物不知数”问题

《孙子算经》提出了中国剩余定理的一个特例。

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问：物几何？答曰：二十三。

术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之，得二百三十三。以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五。一百六以上，以一百五减之，即得。

——《孙子算经》 南北朝 作者不详

因此这类问题也被称为“物不知数”。

“剪管术”

杨辉在《续古摘奇算法》中又提出了四个类似的问题，分别称为“三五七数”“七八九数”“十一十二十三”“二五七九”，并将算法称为“剪管术”（或“翦管术”），但是也没有提到其中的“乘率”如何获取。

物不知总数，只云三三数之剩二，五五数之剩三，七七数之剩二。问：本总数几何？_孙子。

答曰：二十三。

解题_{俗名“秦王暗点兵”，犹“覆射之术”，或“过一百五数”，须于题内云知。}

剪管

术曰：三数剩一，下七十_{题内剩二，下百四十。}；五数剩一，下二十一_{题内剩三，下六十三。}；七数剩一，下十五_{题内剩二，下三十}。三位并之_{得二百三十三。}，满一百五数去之_{减两个一百五。}，馀_二十三为答数。

今续四问。

用工不知其数。差人支犒，每三人支肉一斤，剩零五两八铢_{乃三数剩二。注：古制，一斤十六两，一两二十四铢。剩下零头为五两八铢即剩下三分之一斤，也就是人数三个一组剩两个。}；每五人支钱一贯，剩零四百_{是五数剩三。注：一千钱为一贯。}；每七人支酒一掇，恰撞成掇_{是七数无剩。}问：总工所支各几何？

答曰：九十八人，钱一十九贯六百，酒十四掇，肉三十二斤一十两十六铢。

草曰：三剩二_{下百四十。}，五剩三_{下六十三。}，七无剩_不下。。并之_{得二百三。}减一百五，馀九十八工。以二百乘工数为钱，七除工数为酒，三除工数为肉。

七数剩一，八数剩二，九数剩三。问：本总数几何？

答曰：四百九十八。

术曰：七馀一，下二百八十八_{题内馀一。}；八馀一，下四百四十一_{题内馀二，下八百八十二。}；九馀一，下二百八十_{题内馀三，下八百四十。}。并之_{二千一十。}，满五百四去之_{去三个五百四。}，馀_{四百九十八。}合问。

十一数馀三，十二数馀二，十三数馀一。问：元总。_{注：推测与下段的“问：元总数几何”相同。}

答曰：一十四。

术曰：十一馀一，下九百三十六_{题内馀三，下二千八百八。}；十二馀一，下一千五百七十三_{题内馀二，下三千一百四十六。}；十三馀一，下九百二十四_{题内馀一。}。并之_{六千八百七十八。}，满总法一千七百一十六，去之_{去四个一千七百一十六。}，馀_一十四合问。

二_{注：书影是“一”，但按上下文应为“二”，故订正。}数馀一，五数馀二，七数馀三，九数馀四。问：元总数几何？

答曰：一百五十七。

术曰：二数馀一，下三百一十五_{题内馀一。}；五数馀一，下一百二十六_{题内馀二，下二百五十二。}；七数馀一，下五百四十_{题内馀三，下一千六百二十。}；九数馀一，下二百八十_{题内馀四，下一千一百二十。}。并之_{三千三百〇七。}，满总法六百三十去之_{去五个六百三十。}馀_百五十七为答数，合问。

——《续古摘奇算法》 南宋 杨辉 注者不详，可能为自注或刊刻者注

大衍总数术

秦九韶在《数书九章》中首次给出了其一个通用算法。

由于引文中的术语密度太大，很容易看错，为了便于断句，现代不常用的名词术语添加引号标注。

……所有“元数”、“收数”、“通数”三格，皆有复乘求“定”之理，悉可入之。……

以“定”相乘为“衍母”。以各“定”约“衍母”，得各“衍数”。诸“衍数”各满“定母”去之，不满曰“奇”。以“奇”与“定”，用“大衍求一”入之，以求“乘率”。

……

——《数学九章》 南宋 秦九韶

这里就提出了得到新的模数（“衍母”） [math]\displaystyle{ M = \prod_i m_i }[/math] 、新模数与各模数的商（以“定”约“衍母”得“衍数”） [math]\displaystyle{ M_i }[/math] 、这个商对模数的余数（“衍数”再去“定母”后的“奇”） [math]\displaystyle{ M_i \bmod m_i }[/math] ，然后通过“大衍求一术”求 [math]\displaystyle{ M_i^{-1} \pmod{m_i} }[/math] 作为系数（“乘率”）。大衍求一术的细节见大衍求一术#历史。