查看“︁中国剩余定理”︁的源代码

[[分类:同余理论]]
[[分类:以秦九韶命名]]
[[分类:以孙子命名]]
{{InfoBox
|name=中国剩余定理
|eng_name=Chinese remainder theorem
|aliases=CRT,孙子定理,Sunzi's theorem
}}
'''中国剩余定理'''('''Chinese remainder theorem'''， '''CRT''')或'''<ins>孙子</ins>定理'''指模数互质的同余方程组的一种解法。

== 定理 ==

对一次同余方程组

<math>
\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>m_1, m_2, \dots, m_k</math> 两两[[互质]]。

记 <math>m = m_1 m_2 \dots m_k</math> 及 <math>m = m_j M_j</math>，且可求逆得 <math>e_j = M_j M_j^{-1} \equiv 1 \pmod {n_j}</math> ，

则 <math>x\equiv \sum_{j=1}^k e_j a_j \pmod{m}</math> 是其解。

注：前一半的 <math>e_j = M_j M_j^{-1} \equiv 1 \pmod {m_j}</math> 和[[拉格朗日插值法]]中拆分的多项式想法是相似的，结果上必然有

<math>
e_j \equiv
\begin{cases}
1 \pmod{m_i} &, j=i \\
0 \pmod{m_i} &, j\neq i \\
\end{cases}
</math>

这是因为不同的模数都一定能整除 <math>M_j</math> 。

注：算法中需要从 <math>\prod_{m\neq j} n_m \cdot l_m \equiv 1 \pmod {\prod_{m=1}^k n_m}</math> 确定 <math>l_m</math> 的解，这个过程即为[[大衍求一术]]。

== 中国剩余映射 ==

{{InfoBox
|name=中国剩余映射
|eng_name=Chinese remainder map
}}
中国剩余定理建立了一系列模数互质的[[完全剩余系]]与以模数之积为新的模数的完全剩余系之间的双射，称为'''中国剩余映射'''('''Chinese remainder map''')。

<math>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 的同余方程组，“<ins>孙子</ins>定理”一词有时仅指三个同余方程的情况。

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

[[大衍求一术]]是这个完整算法的一个子过程。