Chinese remainder theorem

Description:

• Let $m_1,m_2,...,m_n$ be pairwise relatively prime positive integers greater than 1 and $a_1,a_2,...,a_n$ arbitrary integers.
  • Then the system$\{\begin{array}{l}x\equiv a_1\mathrm{mod}{m}_1\\ x\equiv a_2\mathrm{mod}{m}_2\\ ...\\ x\equiv a_n\mathrm{mod}{m}_n\end{array}$ has a unique solution modulo $m=m_1{m}_2,...,m_n$
  • That is, there is a solution $x$ with $0\le x<m$, and all other solutions are congruent modulo $m$ to this solution

Uniqueness

• Let assume $0<=x,y<m$ be solution, then $m_k|y-x\text{ for all }k=1,2,...,n$ (why?).
• Hence, $m=m_1{m}_2\cdot \cdot \cdot m_n$ and $m|y-x$
  • note $|y-x|<m$, we must have $y-x=0$, or $x=y$

Existence

• Define $M_k=m/m_k$ for $k=1,2,...,n$. We can show $gcd(m_k,M_k)=1$
• Thus, there exists an integer $y_k$ such that $M_k{y}_k\equiv 1\mathrm{mod}{m}_k$
  • Find inverse by ^4b2036
• We can show $x\equiv a_1{M}_1{y}_1+a_2{M}_2{y}_2+\cdot \cdot \cdot +a_n{M}_n{y}_n\mathrm{mod}m$ is a solution