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.

Another approach to CRT is using group isomorphisms. Stating, let $N=pq$ where $p,q$ are co-prime, then $Z_N\simeq Z_p\times Z_q$ and $Z_N^{\ast }\simeq Z_p^{\ast }\times Z_q^{\ast }$. To prove this, take a function $f:Z_N\to (Z_p,Z_q)$ (similarly for multiplicative group) and prove it’s a bijection.

To convert¹ from $Z_p\times Z_q\to Z_N$:

• To convert $(a,b)\to c$, note that $(a,b)$ can be written as $a\cdot (1,0)+b\cdot (0,1)$ mod N.
• Now, find $(1,0)\to 1_p$ and $(0,1)\to 1_q$.
• prerequisite: $\gcd (p,q)=1$, then using extended euclidean algorithm find $pX+qY=1$.
• Note that $pX\equiv 1\mathrm{mod}q,qY\equiv 1\mathrm{mod}p$.
• $c=a\cdot 1_p+b\cdot 1_q\mathrm{mod}N$

Footnotes

1. Introduction to Modern Cryptography: Chapter 9 ↩