中国剩余定理(Chinese Remainder Theorem, CRT)是数论中的一个重要定理,它提供了一种方法来解决一组一元线性同余方程. 这个定理最早出现在中国南北朝时期的数学著作《孙子算经》中,因此在中文数学文献中也被称为孙子定理 (Sunzi's theorem).
中国剩余定理(孙子定理)
设 mi(1⩽i⩽n)m_i (1\leqslant i\leqslant n) 两两互素,则对任意整数 bi,1⩽i⩽nb_i,1\leqslant i\leqslant n,同余方程组
{x≡b1(modm1)x≡b2(modm2)⋯x≡bn(modmn)\left.\left\{\begin{array}{l}x\equiv b_1\pmod{m_1}\\x\equiv b_2\pmod{m_2}\\\cdots\\x\equiv b_n\pmod{m_n}\end{array}\right.\right.
在模 m1m2⋯mnm_1m_2\cdots m_n 同余意义下有唯一解.
孙子分解定理
设 m=m1⋯msm=m_1\cdots m_s,而整数 m1,⋯ ,msm_1,\cdots,m_s 两两互素,则 Zm\mathbf{Z}_m 中的元素 x‾\overline{x} 可以表示为
x‾=b‾1⋅e‾1+⋯+b‾s⋅e‾s\overline{x}=\overline{b}_1 \cdot \overline{e}_1+\cdots+ \overline{b}_s \cdot \overline{e}_s
或者记作坐标
x‾=(b‾1,⋯ ,b‾s)\overline{x}= ( \overline{b}_1 , \cdots, \overline{b}_s )