# Chinese Remainder Theorem/Construction of Solution

## Theorem

Recall the Chinese Remainder Theorem:

Let $b_1, b_2, \ldots, b_r \in \Z$.

Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.

Let $\ds N = \prod_{i \mathop = 1}^r n_i$.

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_r$ $\ds \pmod {n_r}$

has a solution which is unique modulo $N$:

$\exists ! a \in \Z_{>0}: x \equiv a \pmod N$

## Solution

The following is a systematic technique for finding $a$:

For each $i \in \set {1, 2, \ldots, r}$, calculate:

$y_i = \dfrac N {n_i}$

Using Euclid's Algorithm, calculate $z_i$ such that:

$z_i y_i = 1 \pmod {n_i}$

Then:

$x \equiv \ds \sum_{i \mathop = 1}^r b_i y_i z_i$

is a unique solution to the given system of linear congruences.

## Proof

First we demonstrate that $x$ is a solution.

By construction:

 $\ds \forall j \in \set {1, 2, \ldots, r}: \,$ $\ds n_j$ $\divides$ $\ds y_i$ $\ds \leadsto \ \$ $\ds y_i$ $\equiv$ $\ds 0$ $\ds \pmod {n_i}$ $\text {(1)}: \quad$ $\ds \leadsto \ \$ $\ds b_i y_i z_i$ $\equiv$ $\ds 0$ $\ds \pmod {n_i}$

For each $i \in \set {1, 2, \ldots, r}$, we have:

 $\ds x$ $\equiv$ $\ds \sum_{i \mathop = 1}^r b_i y_i z_i$ $\ds \pmod {n_i}$ $\ds$ $\equiv$ $\ds b_i y_i z_i$ $\ds \pmod {n_i}$ from $(1)$: all terms vanish except for one $\ds$ $\equiv$ $\ds b_i$ $\ds \pmod {n_i}$ as $y_i z_i \equiv 1$

Hence:

$\forall i \in \set {1, 2, \ldots, r}: x \equiv b_i \pmod {n_i}$

Thus $x$ is a solution as required.

$\Box$

Now we demonstrate uniqueness up to congruence modulo $N$:

Now suppose there exist $u, v \in \Z$ which are both solutions.

Then:

 $\ds \forall j \in \set {1, 2, \ldots, r}: \,$ $\ds u$ $\equiv$ $\ds b_i$ $\ds \pmod {n_i}$ $\ds v$ $\equiv$ $\ds b_i$ $\ds \pmod {n_i}$ $\ds \leadsto \ \$ $\ds u - v$ $\equiv$ $\ds b_i$ $\ds \pmod {n_i}$ $\ds \leadsto \ \$ $\ds \forall j \in \set {1, 2, \ldots, r}: \,$ $\ds n_1$ $\divides$ $\ds u - v$ $\ds \leadsto \ \$ $\ds \prod_{i \mathop = 1}^r n_i$ $\divides$ $\ds u - v$ as $n_1, n_2, \ldots, n_r$ are pairwise coprime $\ds \leadsto \ \$ $\ds u$ $\equiv$ $\ds v$ $\ds \pmod {\prod_{i \mathop = 1}^r n_i}$ $\ds \leadsto \ \$ $\ds u$ $\equiv$ $\ds v$ $\ds \pmod N$

$\blacksquare$