Chinese Remainder Theorem/General Result

From ProofWiki
Jump to navigation Jump to search



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




Sources