Chinese Remainder Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b, r, s \in \Z$.

Let $r \perp s$ (that is, let $r$ and $s$ be coprime).


Then:

$a \equiv b \pmod {r s}$ if and only if $a \equiv b \pmod r$ and $a \equiv b \pmod s$

where $a \equiv b \pmod r$ denotes that $a$ is congruent modulo $r$ to $b$.


General Result

Let $n_1, n_2, \ldots, n_r$ be positive integers such that $n_i \perp n_j$ for all $i \ne j$ (that is, $\gcd \left\{{n_i, n_j}\right\} = 1$).

Then the system of linear congruences:

$x \equiv b_1 \pmod {n_1}$
$x \equiv b_2 \pmod {n_2}$
$\ldots$
$x \equiv b_r \pmod {n_r}$

has a simultaneous solution which is unique modulo $\displaystyle \prod_{i \mathop = 1}^r n_i$.


Ultrageneral Result

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

Necessary Condition

Suppose $a \equiv b \pmod {r s}$.

Then from Congruence by Divisor of Modulus it follows directly that:

$a \equiv b \pmod r$

and:

$a \equiv b \pmod s$

Note that for this result it is not required that $r \perp s$.

$\Box$


Sufficient Condition

Now suppose that $a \equiv b \pmod r$ and $a \equiv b \pmod s$.

We have by definition of congruence:

$a \equiv b \pmod r \implies \exists k \in \Z: a - b = k r$

From $a \equiv b \pmod s$ we also have that:

$k r \equiv 0 \pmod s$

As $r \perp s$, we have from Common Factor Cancelling in Congruence:

$k \equiv 0 \pmod s$

So:

$\exists q \in \Z: a - b = q s r$

Hence by definition of congruence:

$a \equiv b \pmod {r s}$

$\blacksquare$


Examples

$n \equiv 7 \pmod {12}$ implies $n \equiv 3 \pmod 4$

Let $n \equiv 7 \pmod {12}$.

Then:

$x \equiv 3 \pmod 4$


Warning

Let $r$ not be coprime to $s$.


Then it is not necessarily the case that:

$a \equiv b \pmod {r s}$ if and only if $a \equiv b \pmod r$ and $a \equiv b \pmod s$

where $a \equiv b \pmod r$ denotes that $a$ is congruent modulo $r$ to $b$.


Historical Note

The Chinese Remainder Theorem was found in the Sun Tzu Suan Ching of Sun Tzu, who was active in China sometime between $200$ and $500$ C.E (nobody knows exactly when).

The principle is believed to have been used by Chinese calendar makers as far back as $100$ C.E.


Sources