\[\begin{cases} x \equiv a_1 (\bmod m_1)\\ x \equiv a_2 (\bmod m_2)\\ \vdots\\ x \equiv a_n (\bmod m_n)\\ \end{cases} \]
其中 \(M = \prod^{n}_{i = 1}m_i\), \(m_i\) 互质。
设 \(w_i = \dfrac{M}{m_i}\)，\(p_iw_i + q_im_i = 1\), \(c_i=p_iw_i\)，并且其一定成立。
有 $$x \equiv \sum^n_{i=1}a_ic_i (\bmod M)$$
证明
有 \(w_i\) 与 \(m_i\) 互质，即
\[p_iw_i + q_im_i = 1 \]即
\[c_i + q_im_i = 1 \]即
\[c_i \bmod m_i = 1 \]因为 \(w_i\) 含有 \(m_j(j \in \{1 \dots n\},j \ne i)\)，所以 \(w_i \bmod m_j = 0\)。
整理得
\[\begin{aligned} c_i \equiv 1 (\bmod m_i)\\ w_i \equiv 0(\bmod m_j)\\ j \in \{1 \dots n\},j \ne i \end{aligned} \]将 \(x\) 带回原式得
\[\begin{cases} a_1\equiv \sum^n_{j=1}a_jc_j (\bmod m_1)\\ a_2\equiv \sum^n_{j=1}a_jc_j (\bmod m_2)\\ \vdots\\ a_n\equiv \sum^n_{j=1}a_jc_j (\bmod m_n)\\ \end{cases} \]即
\[\begin{aligned} a_i &\equiv a_1c_1 + a_2c_2 + \dots + a_ic_i + \dots + a_nc_n (\bmod m_i)\\ &\equiv a_ic_i (\bmod m_i)\\ &\equiv a_i(\bmod m_i) \end{aligned} \]该式恒成立。
所以$x = \sum^n_{i=1}a_ic_i $ 是 \(\begin{cases}x \equiv a_1 (\bmod m_1)\\x \equiv a_2 (\bmod m_2)\\\vdots\\x \equiv a_n (\bmod m_n)\\\end{cases}\) 的一组解。
因为 \(M = \prod^{n}_{i = 1}m_i\), 所以 \(x + kM\) 也是一组解。
即
\[x \equiv \sum^n_{i=1}a_ic_i (\bmod M) \]证毕。
换一句话说： 在 \(Z_M\) 中， \(x\) 有唯一解。
标签：剩余,end,CRT,bmod,sum,cases,定理,ic,equiv From： https://www.cnblogs.com/dadidididi/p/17023341.html