Chinese Remainder Theorem - Theorem Statement

Theorem Statement

The original form of the theorem, contained in a third-century AD book The Mathematical Classic of Sun Zi (孫子算經) by Chinese mathematician Sun Tzu and later generalized with a complete solution called Da yan shu(大衍術) in a 1247 book by Qin Jiushao, the Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections) is a statement about simultaneous congruences (see modular arithmetic).

Suppose n1, n2, …, nk are positive integers which are pairwise coprime. Then, for any given sequence of integers a1,a2, …, ak, there exists an integer x solving the following system of simultaneous congruences.

\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &{}\ \ \vdots \\ x &\equiv a_k \pmod{n_k} \end{align}

Furthermore, all solutions x of this system are congruent modulo the product, N = n1n2…nk.

Hence for all, if and only if .

Sometimes, the simultaneous congruences can be solved even if the ni's are not pairwise coprime. A solution x exists if and only if:

All solutions x are then congruent modulo the least common multiple of the ni.

Sun Zi's work contains neither a proof nor a full algorithm. What amounts to an algorithm for solving this problem was described by Aryabhata (6th century; see Kak 1986). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).

A modern restatement of the theorem in algebraic language is that for a positive integer with prime factorization we have the isomorphism between a ring and the direct product of its prime power parts:

Read more about this topic:  Chinese Remainder Theorem

Famous quotes containing the words theorem and/or statement:

    “To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
    —Albert Camus (1913–1960)

    “One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
    —Rebecca West (1892–1983)