Chinese Remainder Theorem (CRT)

The CRT states that if you have

$M=\prod _{i=0}^{n-1}{m}_i$ and

$m_i$ are all co-prime, then every number mod

$M$ is uniquely represented by its remainders mod

$m_i$.

Example

Suppose

$M=420$ and

$\{m_i\}=\{5,7,12\}$.

$$\begin{array}{rl}37& =2\mathrm{mod}5\\ 37& =2\mathrm{mod}7\\ 37& =1\mathrm{mod}12\end{array}$$

This is the only number (mod 420) for which the statements above are true.

Residue Number System

Extending the example above, we can represent

$37$ as

$(2,2,1)$ as a shorthand.

We can then do operations on numbers in this representation, e.g:

$$(2,2,1{)}^2=(2^2,2^2,1^2)=(4,4,1)$$

After doing as much work as we want in this number system, we can convert back to a regular mod

$420$ number.

Consider that if we knew the values of these three special numbers:

$$\begin{array}{rl}{b}_0& =(1,0,0)\\ b_1& =(0,1,0)\\ b_2& =(0,0,1)\end{array}$$

Then we could easily compute:

$$(4,4,1)=4\ast (1,0,0)+4\ast (0,1,0)+1\ast (0,0,1)$$

Taking

$b_0=(1,0,0)$ as an example, this number must be

$0$ under modulo

$7$ and

$12$, and is therefore a multiple of

$7\ast 12=84$:

$$b_0=(1,0,0)=84x$$

Considering the mod

$5$ component (the

$1$ in

$(1,0,0)$), we have:

$$\begin{array}{rl}84x& =1\\ 4x& =1\\ x& =4^{-1}\\ x& =4\mathrm{mod}5\end{array}$$

(

$4^{-1}=4$ can be found using the Extended Euclidean Algorithm.)

Therefore:

$$b_0=84x=84\ast 4=336=-84$$

Following the same method, we obtain:

$$\begin{array}{rl}{b}_0& =-84\\ b_1& =120\\ b_2& =-35\end{array}$$

And:

$$\begin{array}{rl}(4,4,1)& =4\ast (-84)+4\ast 120+1\ast (-35)\\ & =4\ast (120-84)-35\\ & =109\mathrm{mod}420\end{array}$$

We can verify this matches the traditional calculation:

$$\begin{array}{rl}{37}^2& =1369\\ & =109\mathrm{mod}420\end{array}$$

Further Reading

• Chinese Remainder Theorem
• Residue Number System