# Chinese Remainder Theorem/General Result 2

## Theorem

Let $n_1, n_2, \ldots, n_k$ be positive integers.

Let $b_1, b_2, \ldots, b_k$ be integers such that:

$\forall i \ne j: \gcd \set {n_i, n_j} \divides b_i - b_j$

Then the system of linear congruences:

 $\ds x$ $\equiv$ $\ds b_1$ $\ds \pmod {n_1}$ $\ds x$ $\equiv$ $\ds b_2$ $\ds \pmod {n_2}$ $\ds$ $\vdots$ $\ds$ $\ds x$ $\equiv$ $\ds b_k$ $\ds \pmod {n_k}$

has a simultaneous solution which is unique modulo $\lcm \set {n_1, \ldots, n_k}$.

## Proof

### Existence

We prove this by induction on $k$.

#### Basis for the induction

Let $k = 2$.

Let $d = \gcd \set {n_1, n_2}$.

From Bézout's Identity:

$d = s n_1 + t n_2$

for some $s, t \in \Z$.

Let $\tuple {q_1, r}$ and $\tuple {q_2, r}$ be the quotient and remainder of $b_1$ and $b_2$ upon division by $d$.

Then $x = q_1 s n_2 + q_2 t n_2 + r$ is a solution.

#### Induction step

Let $n = \lcm \set {n_2, \ldots, n_k}$.

By the induction hypothesis, the last $k - 1$ congruences are equivalent to a single congruence:

$x \equiv b \pmod n$

for a certain $b \in \Z$ which satisfies $b \equiv b_i \pmod {n_i}$ for all $i \in \set {2, \ldots, k}$.

It remains to be shown that

$\lcm \set {n, n_1} = \lcm \set {n_1, \ldots, n_k}$
$b \equiv b_1 \pmod {\gcd \set {n, n_1} }$

to apply the case $k = 2$ and conclude.

The first statement follows from Lowest Common Multiple is Associative.

$\gcd \set {n, n_1} = \lcm \set {\gcd \set {n_1, n_2}, \ldots, \gcd \set {n_1, n_k} }$

For all $i \in \set {2, \ldots, k}$:

$b \equiv b_i \pmod {n_i}$

and:

$b_i \equiv b_1 \pmod {\gcd \set {n_1, n_i} }$

Thus:

$b \equiv b_1 \pmod {\gcd \set {n_1, n_i} }$

Therefore:

$b \equiv b_1 \pmod {\lcm \set {\gcd \set {n_1, n_2}, \ldots, \gcd \set {n_1, n_k} } }$

$\Box$