Chinese remainder theorem

From Knowino

Jump to: navigation, search

The Chinese remainder theorem is a mathematical result about modular arithmetic. It describes the solutions to a system of linear congruences with distinct moduli. As well as being a fundamental tool in number theory, the Chinese remainder theorem forms the theoretical basis of algorithms for storing integers and in cryptography. The Chinese remainder theorem can be generalized to a statement about commutative rings.

[edit] Theorem statement

The Chinese remainder theorem:

Let positive integers $n_1, \ldots, n_t$ be pairwise relatively prime (it means: no factor greater than one is common to two or more of them), and set $n = n_1 n_2 \cdots n_t$ . Let $a_1, \ldots, a_k$ be integers. Then the system of congruences

$\begin{align} x &\equiv a_1 \pmod{n_1}\\ x &\equiv a_2 \pmod{n_2}\\ &\;\; \vdots \qquad \quad \, \, \, \, \vdots\\ x &\equiv a_t \pmod{n_t}\\ \end{align}$

has solutions, and any two solutions differ by a multiple of $n$ .

[edit] Methods of proof

The Theorem for a system of t congruences to coprime moduli can be proved by mathematical induction on t, using the theorem when $t = 2$ both as the base case and the induction step. We mention two proofs of this case.

[edit] Existence proof

As usual we let $\mathbf{Z}/n$ denote the set of integers modulo n. Suppose that $n 1, n 2$ are coprime. We consider the map f defined by

$x \bmod (n_1 n_2) \mapsto (x \bmod n_1, \, x\bmod n_2) \,$

We claim that this map is injective: that is, if $x \not\equiv y \bmod (n_1 n_2)$ then $x \not\equiv y \bmod n_1$ or $x \not\equiv y \bmod n_2$ . Suppose that $x \equiv y \bmod n_1$ or $x \equiv y \bmod n_2$ . Then each of $n 1$ and $n 2$ divides $x - y$ : but since $n 1$ and $n 2$ are coprime, it follows that their product $n 1 n 2$ divides $x - y$ also.

But the two sets in question, the first consisting of all residue classes modulo $n 1 n 2$ and the second consisting of pairs of residue classes modulo $n 1$ and $n 2$ , have the same number of elements, namely $n 1 n 2$ . So if the map f is injective, it must also be surjective: that is, for every possible pair $(x 1 mod n 1, x 2 mod n 2)$ , there is an $x mod (n 1 n 2)$ mapping to that pair.

[edit] Explicit construction

The existence proof assures us that the solution exists but does not help us to find it. We can do this by appealing to the Euclidean algorithm. If $n 1$ and $n 2$ are coprime, then there exist integers $u 1$ and $u 2$ such that

$u_1n_1 + u_2n_2 = 1 ,\,$

and these can be computed by the extended Euclidean algorithm. We now observe that putting

$x = u_1n_1x_2 + u_2n_2x_1 ,\,$

we have

$x \equiv x_1 \bmod n_1,~~x \equiv x_2 \bmod n_2 . \,$

Some content on this page may previously have appeared on Citizendium.

Chinese remainder theorem

Contents

[edit] Theorem statement

[edit] Methods of proof

[edit] Existence proof

[edit] Explicit construction

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Community

Toolbox