> [!NOTE] Theorem (Chinese Remainder Theorem) > Suppose $(m_{i})_{i=1}^{k}$ is a list of [[Integers|integers]] or [[Natural Numbers|natural numbers]], all of which are pairwise [[Coprime Integers|coprime]]. Then for any list of integers $(a_{i})_{i=1}^{k},$ the system of linear [[Congruence Modulo n|congruences]] $x \equiv a_{i} \;(\text{mod }m_{i}),$ for $1 \leq i \leq k$ has a unique solution modulo $M=\prod_{i=1}^{k} m_{i}.$ **Proof**: (Construction) For $i=1,2\dots,k,$ let $M_{i}=M/m_{i}.$ Since $\gcd(m_{i},m_{j})=1$ for $i\neq j,$ we have $\gcd(m_{i},M_{i})=1.$ Thus by [[Extended Euclidean Algorithm|extended Euclidean algorithm]], the congruence $M_{i}y\equiv {1} \pmod{m_{i}}$ has a unique solution modulo $m_{i}$ - denote $b_{i}.$ Let $x_{0}=\sum_{i=1}^{m} M_{i}b_{i}a_{i} .$ Since $a_{i}M_{i}b_{i}\equiv a_{i} \pmod{m_{i}}$ and $M_{j}\equiv 0 \pmod{m_{i}}$ for $i\neq j,$ it follows that $x_{0}\equiv a_{i} \pmod{m_{i}}$ for $1\leq i\leq k.$ Hence $x_{0}$ is a solution of the system of linear congruences. (Uniqueness) Suppose that $x_{1}$ is any other solution of the system. For $1\leq i\leq k,$ we have $x_{0}\equiv x_{1} \equiv a_{i} \pmod{m_{i}},$ hence, $m_{i}\mid(x_{1}-x_{0}),$ and thus $x_{1}\equiv x_{0} \pmod{M}.$ Therefore, if a solution exists, it is unique modulo $M.$ > [!Example] >Use the Chinese Remainder Theorem to solve the system $\begin{aligned}& x \equiv 2(\bmod 3), \\& x \equiv 3(\bmod 5), \\& x \equiv 2(\bmod 7) .\end{aligned}$ > >Let $M=3 \cdot 5 \cdot 7=105$, then$\begin{aligned}& m_1=3, \quad m_2=5, \quad m_3=7, \\& a_1=2, \quad a_2=3, \quad a_3=2, \\& M_1=35, \quad M_2=21, \quad M_3=15 \text {. } \\&\end{aligned}$ >Solve the following congruences for $b_i$, for $i=1,2$, and $3.$ $\begin{aligned} & 35 b_1 \equiv 1(\bmod 3), \quad 21 b_2 \equiv 1(\bmod 5), \quad 15 b_3 \equiv 1(\bmod 7), \\ & 2 b_1 \equiv 1(\bmod 3), \quad b_2 \equiv 1(\bmod 5), \quad b_3 \equiv 1(\bmod 7), \\ & b_1 \equiv 2(\bmod 3), \quad b_2 \equiv 1(\bmod 5) \text {. } \\ & \end{aligned}$ >Therefore $x \equiv \sum_{i=1}^{3} M_{i}b_{i}a_{i}=233 \equiv 23 \pmod{105}.$