# Chinese remainder theorem

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

This editable Main Article is under development and subject to a disclaimer.

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 ${\displaystyle n_{1},\ldots ,n_{t}}$ be pairwise relatively prime positive integers, and set ${\displaystyle n=n_{1}n_{2}\cdots n_{t}}$. Let ${\displaystyle a_{1},\ldots ,a_{k}}$ be integers. The system of congruences

{\displaystyle {\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 ${\displaystyle 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 ${\displaystyle t=2}$ both as the base case and the induction step. We mention two proofs of this case.

### Existence proof

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

${\displaystyle 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 ${\displaystyle x\not \equiv y{\bmod {n}}_{1}n_{2}}$ then ${\displaystyle x\not \equiv y{\bmod {n}}_{1}}$ or ${\displaystyle x\not \equiv y{\bmod {n}}_{2}}$. Suppose that ${\displaystyle x\equiv y{\bmod {n}}_{1}}$ or ${\displaystyle x\equiv y{\bmod {n}}_{2}}$. Then each of ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ divides ${\displaystyle x-y}$: but since ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ are coprime, it follows that their product ${\displaystyle n_{1}n_{2}}$ divides ${\displaystyle x-y}$ also.

But the two sets in question, the first consisting of all residue classes modulo ${\displaystyle n_{1}n_{2}}$ and the second consisting of pairs of residue classes modulo ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$, have the same number of elements, namely ${\displaystyle n_{1}n_{2}}$. So if the map f is injective, it must also be surjective: that is, for every possible pair ${\displaystyle (x_{1}{\bmod {n}}_{1},x_{2}{\bmod {n}}_{2})}$, there is an ${\displaystyle 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 ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ are coprime, then there exist integers ${\displaystyle u_{1}}$ and ${\displaystyle u_{2}}$ such that

${\displaystyle u_{1}n_{1}+u_{2}n_{2}=1,\,}$

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

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

we have

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