Chinese remainder theorem

The Chinese remainder theorem can be used to solve systems of congruences like:

$$\begin{aligned} x \equiv a_1& \pmod{m_1} \\ &\vdots \\ x \equiv a_k& \pmod{m_n} \\ \end{aligned}$$

Let $m_1, ..., m_n$ be integers greater than 1, these are called the moduli or divisors. Let $m$ be the product of all $m_k$. The theorem than states that if all $m_k$ are pairwise coprime and all $a_k$ are integers such that $0 \le a_k < m_k$, than there is a unique solution $x \pmod{m}$.

Generic solution

To solve a system of congruences, first let

$$m = m_1 \cdot m_2 \cdot \ldots \cdot m_n$$

Next, for $k = 1, 2, \dots, n$ let

$$M_k = \frac{m}{m_k}$$

In other words, $M_k$ is the product of all the moduli, except $m_k$. Now for every $M_k$, find it’s inverse $y_k$, such that:

$$M_k \cdot y_k \equiv 1 \pmod{m_k}$$

To find the solution $x$ of the system, compute

$$x = a_{1}M_{1}y_{1} + a_{2}M_{2}y_{2} + \ldots + a_{n}M_{n}y_{n} \bmod m$$

Example

Find a solution for the following system of congruences:

$$\begin{aligned} x &\equiv 0 \pmod{3} \\ x &\equiv 1 \pmod{5} \\ x &\equiv 2 \pmod{8} \\ \end{aligned}$$

First calculate $m$:

$$m = 3 \cdot 5 \cdot 8 = 120$$

Next determine all $M_k$:

$$\begin{aligned} M_1 &= \frac{m}{m_1} = \frac{120}{3} = 40 \\ M_2 &= \frac{m}{m_2} = \frac{120}{5} = 24 \\ M_3 &= \frac{m}{m_3} = \frac{120}{8} = 15 \\ \end{aligned}$$

Now find the inverse of every $M_k$:

$$\begin{aligned} M_1 \cdot y_1 &\equiv 1 \pmod{m_1} \\ 40 \cdot y_1 &\equiv 1 \pmod{3} \\ y_1 &= 1 \\ \\ M_2 \cdot y_2 &\equiv 1 \pmod{m_2} \\ 24 \cdot y_2 &\equiv 1 \pmod{5} \\ y_2 &= 4 \\ \\ M_3 \cdot y_3 &\equiv 1 \pmod{m_3} \\ 15 \cdot y_3 &\equiv 1 \pmod{8} \\ y_3 &= 7 \\ \end{aligned}$$

Next we compute the solution $x$:

$$\begin{aligned} x &= a_{1}M_{1}y_{1} + a_{2}M_{2}y_{2} + a_{3}M_{3}y_{3} \bmod m \\ x &= 0 \cdot 40 \cdot 1 + 1 \cdot 24 \cdot 4 + 2 \cdot 15 \cdot 7 \bmod 120 \\ x &= 0 + 96 + 210 \bmod 120 \\ x &= 306 \bmod 120 \\ x &= 66 \\ \end{aligned}$$