中国剩余定理

给定一堆两两互质的数 $m_{1}, m_{2}, \dots, m_{k}$ ，解决一个 线性同余方程组：

{\begin{aligned} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ \dots \\ x \equiv a_{k} (\mod m_{k}) \end{aligned}

该方程有公式解。

用 $M = m_{1} m_{2} \dots m_{k}$ ，记 $M_{i} = M / m_{i}$ 。由于 $(M_{i}, m_{i}) = 1$ ，因此可以求出它的逆元 $M_{i}^{- 1}$ ，是关于 $m_{i}$ 的逆元。通解为：

x = a_{1} M_{1} M_{1}^{- 1} + a_{2} M_{2} M_{2}^{- 1} + \dots + a_{k} M_{k} M_{k}^{- 1}

可以用扩展欧几里得算法求逆元 $a x \equiv 1 (\mod m)$ ，注意 $m_{i}$ 不一定是质数，如果是质数直接费马小定理了。

将 $x$ 带入同余方程组显然可以证明对每个式子都成立。

表达整数的奇怪方式

由题意知： $x = k_{i} a_{i} + m_{i}$ ，其中 $a_{i}, m_{i}$ 为给定的数，要求的数为 $k_{i}$ 。列出方程：

k_{i} a_{i} - k_{j} a_{j} = m_{j} - m_{i}

由裴蜀定理可知， $(a_{i}, a_{j}) | m_{j} - m_{i}$ 。