Chinese remainder theorem

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

Advanced ^[?]

This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

[edit intro]

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; for more about this, see the "Advanced" subpage.

1 Theorem statement
2 Methods of proof
- 2.1 Existence proof
- 2.2 Explicit construction

Theorem statement

The Chinese remainder theorem:

Let $n_1, \ldots, n_t$ be pairwise relatively prime positive integers, and set $n = n_1 n_2 \cdots n_t$ . Let $a_1, \ldots, a_k$ be integers. The system of congruences

$\begin{align} x &\equiv a_1 \pmod{n_1}\\ x &\equiv a_2 \pmod{n_2}\\ \vdots &\equiv \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$ .

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.

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_1n_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_1n_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_1n_2$ divides $x-y$ also.

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

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