# Chinese remainder theorem

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.

## Contents |

## [edit] Theorem statement

The Chinese remainder theorem:

Let positive integers be pairwise relatively prime (it means: no factor greater than one is common to two or more of them), and set . Let be integers. Then the system of congruences

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 denote the set of integers modulo *n*.
Suppose that *n*_{1},*n*_{2} are coprime. We consider the map *f* defined by

We claim that this map is injective: that is, if then or . Suppose that or . 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

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

we have

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