Chinese remainder theorem

related topics
{math, number, function}
{country, population, people}

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.

Contents

Theorem statement

The original form of the theorem, contained in a third-century AD book Sun Zi suanjing (孫子算經 The Mathematical Classic by Sun Zi) by Chinese mathematician Sun Tzu and later republished 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 set of integers a1,a2, …, ak, there exists an integer x solving the system of simultaneous congruences

Furthermore, all solutions x to this system are congruent modulo the product N = n1n2nk.

Hence x \equiv y \pmod{n_i} for all 1\leq i \leq k, if and only if x \equiv y \pmod{N}.

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.

An alternative method for solving similar systems of equations 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 constructive algorithm to find the solution

The following algorithm only applies if the ni's are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)

Full article ▸

related documents
Cauchy–Schwarz inequality
Trace (linear algebra)
Locally compact space
Division (mathematics)
Isomorphism
Unlambda
String (computer science)
Rice's theorem
Logical connective
Miranda (programming language)
Brute-force search
Elementary algebra
Ideal (ring theory)
Abel–Ruffini theorem
Transposition cipher
Gödel's completeness theorem
Natural logarithm
Power series
Field extension
Preadditive category
Convergence of random variables
Holomorphic function
Merge sort
NP-complete
Axiom schema of specification
J (programming language)
Horner scheme
Splay tree
Euler–Mascheroni constant
Normed vector space