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.

From GCD and LCM Distribute Over Each Other:

$\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$

Uniqueness

This theorem requires a proof. In particular: Intersection of Congruence Classes and Principle of Mathematical Induction You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.