给你一个同余方程组:
\[\begin{cases}
x\equiv b_1(\text{mod}\ c_1)\\
x\equiv b_2(\text{mod}\ c_2)\\
\dots\\
x\equiv b_n(\text{mod}\ c_n)
\end{cases}
\]
其中 \(c_i\) 两两互素,求解。
我们令 \(M = \displaystyle\prod^n_{i=1}c_i\)。
然后令 \(m_i = \dfrac{M}{c_i}\)。
然后,对每个 \(m_i\),求其逆元 \(k_i\)。
即 \(m_ik_i\equiv 1(\text{mod}\ c_i)\)
构造解 \(x = \displaystyle\sum^n_{i = 1}b_ik_im_i\)
验证是否成立:
\(x\equiv \displaystyle\sum^n_{j = 1}b_jk_jm_j\equiv \displaystyle\sum^n_{j = 1}b_jk_jm_j\equiv\displaystyle\sum^{i - 1}_{j = 1}b_jk_jm_j + b_ik_im_i + \displaystyle\sum^n_{j = i+1}b_jk_jm_j(\text{mod}\ c_i)\)
因为 \(\forall j\in \left[1,i-1\right]\cup\left[i+1, n\right]\),有 \(c_i\mid m_j\)。
因此 \(x\equiv b_ik_im_i\equiv b_i(\text{mod}\ c_i)\)。