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.


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

          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}\\

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 n1,n2 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 n1 and n2 divides xy: but since n1 and n2 are coprime, it follows that their product n1n2 divides xy also.

But the two sets in question, the first consisting of all residue classes modulo n1n2 and the second consisting of pairs of residue classes modulo n1 and n2, have the same number of elements, namely n1n2. So if the map f is injective, it must also be surjective: that is, for every possible pair (x1mod n1,x2mod n2), there is an xmod (n1n2) 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 n1 and n2 are coprime, then there exist integers u1 and u2 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 . \,
Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools