数论 - (扩展) 中国剩余定理

不互质CRT的推导

解线性方程：

$$\begin{cases} x\equiv a_{1} & \pmod{M_{1}} \\ x\equiv a_{2} & \pmod{M_{2}} \\ x\equiv a_{3} & \pmod{M_{3}} \\ & \vdots \\ x\equiv a_{n} & \pmod{M_{n}} \end{cases}$$

取前两项：

$$\begin{cases} x\equiv a_{1} & \pmod{M_{1}} \\ x\equiv a_{2} & \pmod{M_{2}} \end{cases}$$

设 $k$ 乱搞：

$$\begin{cases} x = a_{1} + k_{1} M_{1} &\\ x = a_{2} + k_{2} M_{2} & \end{cases}$$

联立移项：

$$\begin{aligned} & k_{1} M_{1} = ( a_{2} - a_{1} ) + k_{2} M_{2} & \\ & k_{1} M_{1} \equiv a_{2} - a_{1} & \pmod{M_{2}} \end{aligned}$$

令 $g = \gcd(M_{1}, M_{2})$ ，有：

$$\begin{aligned} k_{1} \frac{M_1}{g} & \equiv \frac{a_{2} - a_{1}}{g} & \pmod{\frac{M_{2}}{g}} \\ k_{1} & \equiv \frac{a_{2} - a_{1}}{g} \cdot (\frac{M_1}{g})^{-1} & \pmod{\frac{M_{2}}{g}} \end{aligned}$$

令 $K = \frac{a_{2} - a_{1}}{g} \cdot (\frac{M_{1}}{g})^{-1}$ （上式左侧），带回：

$$\begin{aligned} k_{1} & = c \cdot \frac{M_{2}}{g} + K \\ x & = a_{1} + k_{1} M_{1} \\ & = a_{1} + ( c \cdot \frac{M_{2}}{g} + K ) \cdot M_{1} \\ & = a_{1} + c \cdot \frac{M_{1}M_{2}}{g} + K \cdot M_{1} \\ x & \equiv a_{1} + K \cdot M_{1} \pmod{\frac{M_{1}M_{2}}{g}} \end{aligned}$$

综上：

$$\begin{aligned} \begin{cases} x\equiv a_{1} & \pmod{M_{1}} \\ x\equiv a_{2} & \pmod{M_{2}} \end{cases} \end{aligned} \Rightarrow \begin{aligned} \begin{cases} g & = \gcd (M_{1}, M_{2}) \\ K & = \frac{a_{2} - a_{1}}{g} \cdot (\frac{M_1}{g})^{-1} & \\ x & \equiv a_{1} + K \cdot M_{1} \pmod{\mathrm{lcm}(M_{1}, M_{2})} \end{cases} \end{aligned}$$