中国剩余定理笔记

Post author: BeiYu
Post link: <a href="https://blog.bj-yan.top/algorithm-chinese-remainder-theorem/" title="中国剩余定理笔记">https://blog.bj-yan.top/algorithm-chinese-remainder-theorem/
Copyright Notice: All articles in this blog are licensed under <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/en" rel="noopener" target="_blank"> BY-NC-SA unless stating additionally.

中国剩余定理

${\begin{matrix} x \equiv a_{1} mod m_{1} \\ x \equiv a_{2} mod m_{2} \\ \dots \\ x \equiv a_{n} mod m_{n} \end{matrix}$
其中 $m_{i}$ 两两互质
$M = \prod_{i = 0}^{n} m_{i}, M_{i} = \frac{M}{m_{i}}$
$x = \sum_{i = 0}^{n} a_{i} M_{i} M_{i}^{- 1} (\mod m_{i})$

扩展中国剩余定理

模数不互质的时候
$x \equiv a_{1} mod m_{1}$
$x \equiv a_{2} mod m_{2}$
也就是
$x = k_{1} m_{1} + a_{1} = k_{2} m_{2} + a_{2}$
$∴ k_{1} m_{1} = (a_{2} - a_{1}) + k_{2} m_{2}$
即 $k_{1} m_{2} \equiv (a_{2} - a_{1}) mod m_{2}$
让 $d = (m_{1}, m_{2})$
即 $k_{1} \frac{m_{1}}{d} \equiv \frac{(a_{2} - a_{1})}{d} mod \frac{m_{2}}{d}$
这样就可以得到 $k_{1} = k^{'} \frac{m_{2}}{d} + \frac{a_{2} - a_{1}}{d} (\frac{m_{1}}{d})^{- 1} (\mod \frac{m_{2}}{d})$
令 $t = \frac{a_{2} - a_{1}}{d} (\frac{m_{1}}{d})^{- 1} (\mod \frac{m_{2}}{d})$
带回原式得 $x = (k^{'} \frac{m_{2}}{d} + t) m_{1} + a_{1}$
即可并成 $x = k^{'} \frac{m_{1} m_{2}}{d} + t m_{1} + a_{1}$
即 $x \equiv a mod m$ ，其中 $a = t m_{1} + a_{1}, m = \frac{m_{1} m_{2}}{d}$