Chinese Remainder Theorem (CRT)

Let $n_1,\dots ,n_k$ be integers greater than $1$, and $N={\prod }_{i=1}^k{n}_i$. If the $n_i$ are pair-wise co-prime, and if $a_1,\dots ,a_k$ are any integers, then the system

$$\begin{array}{rl}x& \equiv a_1(\mathrm{mod}{n}_1)\\ & ⋮\\ x& \equiv a_k(\mathrm{mod}{n}_k)\end{array}$$

has a solution, and any two solutions, say $x_1$ and $x_2$, satisfy $x_1\equiv x_2(\mathrm{mod}N)$

A trivial case is if

$$\begin{array}{rl}x& \equiv a(\mathrm{mod}{n}_1)\\ & ⋮\\ x& \equiv a(\mathrm{mod}{n}_k)\end{array}$$

then we have $x\equiv a(\mathrm{mod}N)$

To construct a solution, let $N_i=N/n_i$ be the product of all moduli but one. As the $n_i$ are pair-wise co-prime, $N_i$ and $n_i$ are co-prime. Thus Bezout's identity applies, and there exist integers $M_i$ and $m_i$ such that

$$M_i{N}_i+m_i{n}_i=1$$

A solution of the system of congruences is

$$x=\sum _{i=1}^k{a}_i{M}_i{N}_i$$

In fact, as $N_j$ is a multiple of $n_i$ for $i\ne j$, we have

$$x\equiv a_i{M}_i{N}_i\equiv a_i(1-m_i{n}_i)\equiv a_i(\mathrm{mod}{n}_i)$$

Note

We can use extended Euclidean algorithm to calculate $M_i$ and $m_i$