Chinese Remainder Theorem, deriving the solution

Suppose we have a system of congruences with different moduli:

$$ x ≡ b_1 \mod n_1, x ≡ b_2 \mod n_2, $$ $$ \ldots, x ≡ b_k \mod n_k $$

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 using lemma, we can conclude there exists an inverse:

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

Since \(N_i\) contains a factor of \(n_j\) where \(i \ne j\), then:

$$ N_iN_i^{-1} ≡ 0 \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 \mod n_1, A ≡ b_2 \mod n_2, $$ $$ \ldots, A ≡ b_k \mod n_k $$

Which means \(A\) is a valid solution for \(x\). Now let \(y ≡ b_i \mod n_i\), \(x-y ≡ 0 \mod 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