Chinese Remainder Theorem, deriving the solution

Suppose we have a system of congruences with different moduli:

$$\begin{gather} x ≡ b_1 \bmod n_1, \quad x ≡ b_2 \bmod n_2, \\ \ldots, \quad x ≡ b_k \bmod n_k \end{gather}$$

The \(\gcd\) of all \(n_i\) pairs is 1. Let's define \(N\) as:

$$ N = n_1 n_2 n_3 \ldots n_k $$

And let's define \(N_i\) as:

$$ N_i = \frac{N}{n_i} $$

\(N_3\) is the multiplication of all \(n_i\) except \(n_3\). Since \((n_1, n_3)=1\) and \((n_2, n_3)=1\), then \((n_1n_2, n_3)=1\) using this lemma. This way we can also derive \((n_1n_2n_4, n_3)=1\), and we can further say \((N_3,n_3)=1\). By similar reasoning, we can say the same for any \(N_i\):

$$ (N_i, n_i) = 1 $$

Using this lemma, we can conclude there exists an inverse:

$$ N_iN_i^{-1} ≡ 1 \mod n_i $$

Since \(b_i ≡ b_i \bmod n_i\):

$$ N_iN_i^{-1} b_i ≡ b_i \mod n_i $$

Since \(N_j\) contains a factor of \(n_i\) where \(i \ne j\), then:

$$\begin{gather} N_jN_j^{-1} ≡ 0 \mod n_i \\ N_jN_j^{-1}b_j ≡ 0 \mod n_i \end{gather}$$

This means:

$$ N_iN_i^{-1} b_i + N_jN_j^{-1}b_j ≡ b_i \mod n_i $$

Similarly:

$$ N_iN_i^{-1} b_i + N_jN_j^{-1}b_j ≡ b_j \mod n_j $$

Consider:

$$ A = N_1N_1^{-1}b_1 + N_2N_2^{-1}b_2 + \ldots + N_kN_k^{-1}b_k $$

If we take mod \(n_1\):

$$ A = b_1 + 0 + \ldots + 0 $$

If we take mod \(n_2\):

$$ A = 0 + b_2 + \ldots + 0 $$

If we take mod \(n_k\):

$$ A = 0 + 0 + \ldots + b_k $$

This means:

$$ A ≡ b_1 \bmod n_1, A ≡ b_2 \bmod n_2, $$ $$ \ldots, A ≡ b_k \bmod n_k $$

Which means \(A\) is a valid solution for \(x\). Now let \(y ≡ b_i \bmod n_i\), \(x-y ≡ 0 \bmod n_i\). If \(n_1 | (x-y)\), \(n_2 | (x-y)\), ..., \(n_k | (x-y)\), then using this lemma we can conclude \(N|(x-y)\), or:

$$ x ≡ y \mod N $$

This means that the solution is unique, meaning that there is only one solution modulo \(N\).

Deriving The Solution For The Chinese Remainder Theorem