Chinese Remainder Theorem/General Result
It has been suggested that this page or section be merged into Solution to Simultaneous Linear Congruences. 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 {{Mergeto}} from the code. |
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. |
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Chinese remainder theorem
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Chinese remainder theorem