Let \(n_1, n_2, \dots, n_k\) be pairwise coprime positive integers, and let \(b_1, b_2, \dots, b_k\) be any integers. Then the system of congruences
$$
\begin{aligned}
x &\equiv b_1 \pmod{n_1} \\
x &\equiv b_2 \pmod{n_2} \\
&\;\vdots \\
x &\equiv b_k \pmod{n_k}
\end{aligned}
$$
has a unique solution modulo \(N = n_1 n_2 \cdots n_k\).
Proof
Let \(N = n_1n_2...n_k\) and let \(N_i = N/n_i\). We claim that
$$
\begin{align*}
\gcd(n_i,N_i)=1.
\end{align*}
$$
To see this, suppose that wasn’t the case and let \(d \mid N_i\) and \(d \mid n_i\). We will show that \(d = 1\). Since all of the \(n_j\)s in the product \(N_i\) are relatively prime, then \(d\) must divide some \(n_j\) where \(j \neq i\). (This is because \(N_i = N/n_i\) so \(n_i\) is not in the product). But since \(d \mid n_i\), then this implies that
$$
\begin{align*}
d \mid (n_i, n_j) = 1
\end{align*}
$$
\(n_i\) and \(n_j\) are coprime by definition. Therefore, \(d = 1\) and thus \(\gcd(n_i,N_i) = 1\). Recall that by Euclid, since the gcd is 1, then we can write
$$
\begin{align*}
N_i x + n_i y &= 1 \\
N_i x - 1 &= n_i y
\end{align*}
$$
for some variables \(x_i\) and \(y_i\). But then this just implies that
$$
\begin{align*}
N_ix_i \equiv 1 \pmod{n_i}
\end{align*}
$$
So \(x_i\) is the inverse of \(N_i\) module \(n_i\). Now, recall that by definition \(N_i = N/n_i\). So \(N_i\) is the product of all \(n_j\) such that \(j \neq i\). So we have \(n_j \mid N_i\). This means that we can write
$$
\begin{align*}
N_ix_i \equiv 0 \pmod{n_j} \quad \text{ for } i \neq j
\end{align*}
$$
Now, consider the expression
$$
\begin{align*}
x = x_1N_1b_1 + x_2N_2b_2 + \cdots + x_kN_kb_k
\end{align*}
$$
We will show that \(x \equiv b_i \pmod{n_i}\) for each \(i = 1,2,...,k\). Fix an index \(i\). Now reduce \(x\) modulo \(n_i\)
$$
\begin{align*}
x \equiv x_1N_1b_1 + x_2N_2b_2 + \cdots + x_kN_kb_k \pmod{n_i}
\end{align*}
$$
Recall that
- when \(j \neq i\), we showed that \(N_j\) is divisible by \(n_i\) and so \(N_j \equiv 0 \pmod{n_i}\) and therefore \(x_jN_jb_j \equiv 0 \pmod{n_i}\)
- when \(j = i\), we defined \(x_i\) such that \(x_iN_i \equiv 1 \pmod{n_i}\). So \(x_iN_ib_i \equiv b_i \pmod{n_i}\)
Therefore, for all \(i = 1,...,k\),
$$
\begin{align*}
x &\equiv 0 + \cdots + 0 + x_iN_ib_i + 0 + \cdots + 0 \pmod{n_i} \\
&\equiv b_i \pmod{n_i}
\end{align*}
$$
This shows that \(x\) satisfies each congruence \(x \equiv b_i \pmod{n_i}\). This proves the existence part of the theorem. For the uniqueness part, suppose that \(x\) and \(y\) are both solutions. Therefore, for all \(i = 1,\cdots,k\)
$$
\begin{align*}
x &\equiv b_i \pmod{n_i} \\
y &\equiv b_i \pmod{n_i}
\end{align*}
$$
But then this implies (by the modular arithmetic properties that)
$$
\begin{align*}
x-y &\equiv 0 \pmod{n_i}
\end{align*}
$$
But this means that \(n_i \mid x - y\). So \(x - y\) is a multiple of \(n_i\) for all \(i = 1,...,k\). But the \(n_i\)s are relatively coprime. This implies that \(x - y\) must divide their product. In other words
$$
\begin{align*}
x-y \mid N
\end{align*}
$$
But this just says that
$$
\begin{align*}
x \equiv y \pmod{N}
\end{align*}
$$
Example
Solve
$$
\begin{align*}
x &\equiv 1 \pmod{3} \\
x &\equiv 2 \pmod{4} \\
x &\equiv 4 \pmod{5}
\end{align*}
$$
Using CRT, let \(n_1 = 3\), \(n_2 = 4\) and \(n_3 = 5\). We also want to let
$$
\begin{align*}
N &= 3 \cdot 4 \cdot 5 = 60 \\
N_1 &= n_2n_3 = 20 \\
N_2 &= n_1n_3 = 15 \\
N_3 &= n_1n_2 = 12
\end{align*}
$$
Next, we want to find \(x_1, x_2\) and \(x_3\) such that
$$
\begin{align*}
N_1x_1 \equiv 1 \pmod{n_1} \\
N_2x_2 \equiv 1 \pmod{n_2} \\
N_3x_3 \equiv 1 \pmod{n_3}
\end{align*}
$$
In other words,
$$
\begin{align*}
20x_1 \equiv 1 \pmod{3} \\
15x_2 \equiv 1 \pmod{4} \\
12x_3 \equiv 1 \pmod{5}
\end{align*}
$$
Solving equation \(1\)
$$
\begin{align*}
20x_1 &\equiv 1 \pmod{3} \\
2x_1 &\equiv 1 \pmod{3}
\end{align*}
$$
so
$$
\begin{align*}
x_1 \equiv 2 \pmod{3}
\end{align*}
$$
For equation \(2\),
$$
\begin{align*}
15x_2 \equiv 1 \pmod{4} \\
3x_2 \equiv 1 \pmod{4}
\end{align*}
$$
so
$$
\begin{align*}
x_2 \equiv 3 \pmod{4}
\end{align*}
$$
Finally,
$$
\begin{align*}
12x_3 \equiv 1 \pmod{5} \\
2x_3 \equiv 1 \pmod{5}
\end{align*}
$$
so
$$
\begin{align*}
x_3 \equiv 3 \pmod{5}
\end{align*}
$$
The actual solution is given by
$$
\begin{align*}
x &= x_1N_1b_1 + x_2N_2b_2 + x_3N_3b_3 \\
&= 2\cdot 20 \cdot 1 + 3 \cdot 15 \cdot 2 + 3 \cdot 12 \cdot 4 \\
&= 214
\end{align*}
$$
So \(x = 214\) should satisfy every congruence. Moreover, since we’re working module \(60\), then we can further reduce this to
$$
\begin{align*}
x \equiv 34 \pmod{60}
\end{align*}
$$
References