Note -「The Construction of Chinese Remainer Theorem」

cirnovsky /

原来的标题是:『「水」CRT 的构造本质』。

对于一个单元线性同余方程组 xai(modri)x\equiv a_i\pmod{r_i},考虑构造一个 {ci}\{c_i\} 使得 ij\forall i\neq j,有 ci0(modrj)c_i\equiv0\pmod{r_j},且 ci1(modri)c_i\equiv1\pmod{r_i},那么一定存在解 xaici(modri)x\equiv\sum a_ic_i\pmod{\prod r_i}

给出一种构造方法:令 mi=ririm_i=\frac{\prod r_i}{r_i},则 cimi×mi1c_i\equiv m_i\times m_i^{-1},其中 mi1m_i^{-1}mim_irir_i 的乘法逆元(但运算结果不作取模),显然满足上述性质,这就是 Chinese Remainder Theorem 的构造本质。