Chinese Remainder Theorem/General Result 2

From ProofWiki
Jump to: navigation, search

Theorem

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

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

$\forall i \ne j: \gcd \left({n_i, n_j}\right) \mathrel \backslash b_i - b_j$

where $\backslash$ denotes divisibility.


Then the system of linear congruences:

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

has a simultaneous solution which is unique modulo $\lcm \left({n_1, \ldots, n_k}\right)$.


Proof

Existence

We prove this by induction on $k$.


Basis for the induction

Let $k = 2$.

Let $d = \gcd \left({n_1, n_2}\right)$.

By Bézout's Lemma, there exist $s, t \in \Z$ such that $d = s n_1 + t n_2$.

Let $\left({q_1, r}\right)$ and $\left({q_2, r}\right)$ 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 \left({n_2, \ldots, n_k}\right)$.

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 \left\{ {2, \ldots, k}\right\}$.

It remains to be shown that

$\lcm \left({n, n_1}\right) = \lcm \left({n_1, \ldots, n_k}\right)$
$b \equiv b_1 \pmod {\gcd \left({n, n_1}\right)}$

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 \left({n, n_1}\right) = \lcm \left({\gcd \left({n_1, n_2}\right), \ldots, \gcd \left({n_1, n_k}\right)}\right)$

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

$b \equiv b_i \pmod {n_i}$

and:

$b_i \equiv b_1 \pmod {\gcd \left({n_1, n_i}\right)}$


Thus:

$b \equiv b_1 \pmod {\gcd \left({n_1, n_i}\right)}$

Therefore:

$b \equiv b_1 \pmod {\lcm \left({\gcd \left({n_1, n_2}\right), \ldots, \gcd \left({n_1, n_k}\right)}\right)}$

$\Box$


Uniqueness