# Chinese remainder theorem  Main Article Discussion Related Articles  [?] Bibliography  [?] External Links  [?] Citable Version  [?] Advanced [?] This editable Main Article is under development and 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.

## 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{aligned}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{aligned}} 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}}_{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}{\bmod {n}}_{1},x_{2}{\bmod {n}}_{2})$ , there is an $x{\bmod {n}}_{1}n_{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

$u_{1}n_{1}+u_{2}n_{2}=1,\,$ and these can be computed by the extended Euclidean algorithm. We now observe that putting

$x=u_{1}n_{1}x_{2}+u_{2}n_{2}x_{1},\,$ we have

$x\equiv x_{1}{\bmod {n}}_{1},~~x\equiv x_{2}{\bmod {n}}_{2}.\,$ 