已知
$$ \left{ \begin{align} x \equiv \ & b_{1} \ \mathrm{mod} , m_{1} \ x \equiv \ & b_{2} \ \mathrm{mod} , m_{2} \ & \vdots \ x \equiv \ & b_{k} \ \mathrm{mod} , m_{k} \end{align} \right. $$
记
- $M_{k}=\frac{\prod m_{i}}{m_{k}}$
- $M’{k}$ 为 $M{k}$ 在 mod $m_{k}$ 意义下的逆元 aka $M_{k}’=M_{k}^{-1} \ \mathrm{mod},m_{k}$
则同余方程组的解为
$$ x \equiv \sum_{i=1}^{k} b_{i}M_{i}M’{i} \ \mathrm{mod},\prod m{i} $$
CRT is more than 解方程组
CRT 不仅可以解同余方程组，最本质在于可以对同一个变量整合模数 比如 $a^{7}\equiv a\ \mathrm{mod},7,a^{7}\equiv a \ \mathrm{mod},9 \xRightarrow{\mathrm{CRT}} a^{7}\equiv a \cdot 9 \cdot 4+a\cdot7\cdot 4\equiv64a\equiv a\ \mathrm{mod},63$