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 n₁, n₂, …, n_k are positive integers which are pairwise coprime. Then, for any given sequence of integers a₁,a₂, …, a_k, there exists an integer x solving the following system of simultaneous congruences.

Furthermore, all solutions x of this system are congruent modulo the product, N = n₁n₂…n_k.

Hence for all, if and only if .

Sometimes, the simultaneous congruences can be solved even if the n_i'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 n_i.

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: