Note -「The Construction of Chinese Remainer Theorem」
原来的标题是:『「水」CRT 的构造本质』。
对于一个单元线性同余方程组 x≡ai(modri),考虑构造一个 {ci} 使得 ∀i=j,有 ci≡0(modrj),且 ci≡1(modri),那么一定存在解 x≡∑aici(mod∏ri)。
给出一种构造方法:令 mi=ri∏ri,则 ci≡mi×mi−1,其中 mi−1 是 mi 模 ri 的乘法逆元(但运算结果不作取模),显然满足上述性质,这就是 Chinese Remainder Theorem 的构造本质。