Chinese Remainder Theorem

"In addition to being a theorem and an algorithm, we would suggest to the reader that the Chinese remainder theorem is also a state of mind." - "Introduction to Mathematical Cryptography" by Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman

Problem: $x\equiv a\mathrm{mod}m,x\equiv b\mathrm{mod}n$ where $\gcd (m,n)=1$, find $x$.

Proof that solution exists:

• write $x$ as $x=a+my\mathrm{mod}m$[]
• put into equation 2, $a+my\equiv b\mathrm{mod}n⟹my\equiv (b-a)\mathrm{mod}n$
• since $\gcd (m,n)=1$, then there must exists $m{m}^{\prime }=1\mathrm{mod}n$.
• multiplying by $m^{\prime }$ on both sides, we get $y\equiv m^{\prime }(b-a)\mathrm{mod}n$
• $y=m^{\prime }(b-a)+nz$, putting into eq (1), x is of form: $a+m{m}^{\prime }(b-a)+mnz$

Proof that solution is unique:

• In modulo arithmetic, if $c\equiv c^{\prime }\mathrm{mod}m$, then $m|(c-c^{\prime })$, then let $c\equiv c^{\prime }\mathrm{mod}m⟹m|c-c^{\prime }$ and $c\equiv c^{\prime }\mathrm{mod}n⟹n|c-c^{\prime }$
• then $mn|(c-c^{\prime })$, thus $c\equiv c^{\prime }\mathrm{mod}mn$. Thus, $c,c^{\prime }$ are same modulo $mn$.

This can be easily generalised to arbitrary congruences with each pairwise modulo are co-prime, i.e. $\gcd (m_i,m_j)=1$. There’s a very beautiful general solution to CRT.