# 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](https://en.wikipedia.org/wiki/Coprime_integers), 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{align*}
37 &= 2 \mod 5 \\
37 &= 2 \mod 7 \\
37 &= 1 \mod 12
\end{align*}

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{align*}
b_0 &= (1, 0, 0) \\
b_1 &= (0, 1, 0) \\
b_2 &= (0, 0, 1)
\end{align*}

Then we could easily compute:

$$(4,4,1) = 4*(1,0,0) + 4*(0,1,0) + 1*(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*12=84$:

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

Considering the mod $5$ component (the $1$ in $(1,0,0)$), we have:

\begin{align*}
84x &= 1 \\
4x &= 1 \\
x &= 4^{-1} \\
x &= 4 \mod 5
\end{align*}

($4^{-1}=4$ can be found using the [Extended Euclidean Algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).)

Therefore:

$$b_0 = 84x = 84 * 4 = 336 = -84$$

Following the same method, we obtain:

\begin{align*}
b_0 &= -84 \\
b_1 &= 120 \\
b_2 &= -35
\end{align*}

And:

\begin{align*}
(4,4,1) &= 4 * (-84) + 4 * 120 + 1 * (-35) \\
&= 4 * (120 - 84) - 35 \\
&= 109 \mod 420
\end{align*}

We can verify this matches the traditional calculation:

\begin{align*}
37^2 &= 1369 \\
&= 109 \mod 420
\end{align*}

## Further Reading

- [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
- [Residue Number System](https://en.wikipedia.org/wiki/Residue_number_system)