Chinese Remainder Theorem/Corollary

From ProofWiki
Jump to navigation Jump to search


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$).

Let $N = n_1 \cdots n_r$.

For an integer $k$, let $\Z / k \Z$ denote the ring of integers modulo $k$.

Then we have a ring isomorphism:

$\Z / N \Z \simeq \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$


Define a mapping:

$\phi: \Z / N \Z \to \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$


$\phi \left({d \pmod N}\right) = \left({d \pmod {n_1}, \ldots, d \pmod {n_r} }\right)$

Then, by Mappings Between Residue Classes, $\phi$ is well-defined.

By the definition of multiplication and addition in $\Z / k \Z$, $k \in \Z$ we have:

$\left({a \pmod k}\right) + \left({b \pmod k}\right) = \left({a + b}\right) \pmod k$


$\left({a \pmod k}\right) \cdot \left({b \pmod k}\right) = \left({a \cdot b}\right) \pmod k$

Thus taking $k = n_1, \ldots, n_r$ separately we see that $\phi$ is a ring homomorphism.


$\left({a_1 \pmod {n_1}, \ldots, a_r \pmod {n_r} }\right) \in \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$

By the Chinese Remainder Theorem there exists a unique $x \in \Z / N \Z$ such that:

$\phi \left({x}\right) = \left({a_1 \pmod {n_1}, \ldots, a_r \pmod {n_r} }\right)$

Since such an $x$ exists, $\phi$ is surjective.

Since this $x$ is unique modulo $N$, it follows that $\phi$ is injective.