# 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)