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 $\gcd(n_i,n_j)\mid b_i-b_j$ for all $i \ne j$.

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 $\operatorname{lcm}(n_1,\ldots, n_k)$.


Proof

Existence

We prove this by induction on $k$.

Basis for the induction

Let $k=2$.

Let $d=\gcd(n_1,n_2)$.

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

Let $(q_1,r)$ and $(q_2,r)$ be the quotient and remainder of $b_1$ and $b_2$ upon division by $d$.

Then $x=q_1sn_2+q_2tn_2+r$ is a solution.

Induction step

Let $n=\operatorname{lcm}(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\{2,\ldots,k\}$.

It remains to show that

$\operatorname{lcm}(n,n_1)=\operatorname{lcm}(n_1,\ldots,n_k)$
$b\equiv b_1\pmod{\gcd(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(n,n_1)=\operatorname{lcm}(\gcd(n_1,n_2),\ldots,\gcd(n_1,n_k))$

For all $i\in\{2,\ldots,k\}$, $b\equiv b_i\pmod{n_i}$ and $b_i\equiv b_1\pmod{\gcd(n_1,n_i)}$.

Thus $b\equiv b_1\pmod{\gcd(n_1,n_i)}$.

Therefore, $b\equiv b_1\pmod{\operatorname{lcm}(\gcd(n_1,n_2),\ldots,\gcd(n_1,n_k))}$.

$\Box$


Uniqueness