中国剩余定理(孙子定理)

chinese_remainder_theorem2026-08-24 19:46:25

中国剩余定理(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 )

参考

https://oi-wiki.org/math/number-theory/crt/

https://math.fandom.com/zh/wiki/中国剩余定理

本页目录