中国剩余定理
| 中国剩余定理 | |
|---|---|
| 术语名称 | 中国剩余定理 |
| 英语名称 | Chinese remainder theorem |
| 别名 | CRT, 孙子定理, Sunzi's theorem |
中国剩余定理(Chinese remainder theorem， CRT)或孙子定理指模数互质的同余方程组的一种解法。
定理
对一次同余方程组
[math]\displaystyle{ \begin{aligned} a_1 x &\equiv b_1 \pmod {m_1} \\ a_2 x &\equiv b_2 \pmod {m_2} \\ &\dots \\ a_k x &\equiv b_k \pmod {m_k} \end{aligned} }[/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{ e_j = M_j M_j^{-1} \equiv 1 \pmod {n_j} }[/math] ，
则 [math]\displaystyle{ x\equiv \sum_{j=1}^k e_j a_j \pmod{m} }[/math] 是其解。
注：前一半的 [math]\displaystyle{ e_j = M_j M_j^{-1} \equiv 1 \pmod {m_j} }[/math] 和拉格朗日插值法中拆分的多项式想法是相似的，结果上必然有
[math]\displaystyle{ e_j \equiv \begin{cases} 1 \pmod{m_i} &, j=i \\ 0 \pmod{m_i} &, j\neq i \\ \end{cases} }[/math]
这是因为不同的模数都一定能整除 [math]\displaystyle{ M_j }[/math] 。
注：算法中需要从 [math]\displaystyle{ \prod_{m\neq j} n_m \cdot l_m \equiv 1 \pmod {\prod_{m=1}^k n_m} }[/math] 确定 [math]\displaystyle{ l_m }[/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}) }[/math]
琐事
内容
因为《孙子算经》中只提到了一个具体的模 3、5、7 的同余方程组，“孙子定理”一词有时仅指三个同余方程的情况。
后续由秦九韶整理并推广为大衍总数术，除同余方程数可以扩展到多个以外，还涉及模数和系数需要先约分的情况。因此有时也被称为孙子-秦九韶定理。
大衍求一术是这个完整算法的一个子过程。