孙子分解定理

chinese_remainder_theorem/decomposition2026-08-24 19:46:25

设 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 )

其中 b‾i\overline{b}_i 是在模 mim_i 下定义的.

e‾i\overline{e}_i 是在模 mm 下定义的一组正交基,求法见中国剩余定理,满足

ei‾ ej‾=0(i≠j),ei‾2=ei‾,e1‾+⋯+es‾=1‾(1⩽i,j⩽s)\overline{e_{i}}\:\overline{e_{j}}=0\quad(i\neq j),\quad \overline{e_{i}}^{2}=\overline{e_{i}},\quad \overline{e_{1}}+\cdots+\overline{e_{s}}=\overline{1}\quad(1\leqslant i,j\leqslant s)

bib_i 的求法,只需要求 xx 在模 mim_i 下的值,即

bi≡x(modmi)b_i \equiv x \pmod{m_i}

典型示例

m=105=3×5×7m=105=3 \times 5 \times 7

计算 eie_i:e1=70,e2=21,e3=15e_1=70, e_2=21, e_3=15.

则 Z105\mathbf{Z}_{105} 中的元素 x‾\overline{x} 可以表示为

x‾=b‾1⋅70‾+b‾2⋅21‾+b‾3⋅15‾=(b‾1,b‾2,b‾3)\overline{x}= \overline{b}_1 \cdot \overline{70}+ \overline{b}_2 \cdot \overline{21}+\overline{b}_3 \cdot \overline{15} =( \overline{b}_1 , \overline{b}_2, \overline{b}_3 )

例如

23≡2⋅70+3⋅21+2⋅15(mod105)1≡1⋅70+1⋅21+1⋅15(mod105)104≡2⋅70+4⋅21+6⋅15(mod105)0≡0⋅70+0⋅21+0⋅15(mod105)\begin{aligned} 23 \equiv 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 \pmod{105} \\ 1 \equiv 1 \cdot 70 + 1 \cdot 21 + 1 \cdot 15 \pmod{105} \\ 104 \equiv 2 \cdot 70 + 4 \cdot 21 + 6 \cdot 15 \pmod{105} \\ 0 \equiv 0 \cdot 70 + 0 \cdot 21 + 0 \cdot 15 \pmod{105} \end{aligned}

写成坐标形式

23=(2‾,3‾,2‾)1=(1‾,1‾,1‾)104=(2‾,4‾,6‾)0=(0‾,0‾,0‾)\begin{aligned} 23 = ( \overline{2} , \overline{3}, \overline{2} )\\ 1 = ( \overline{1} , \overline{1}, \overline{1} )\\ 104 = ( \overline{2} , \overline{4}, \overline{6} )\\ 0 = ( \overline{0} , \overline{0}, \overline{0} )\\ \end{aligned}

本页目录