Chinese remainder theorem

Suppose we have a set of n congruencesMathworldPlanetmathPlanetmathPlanetmath of the form


where p1,p2,,pn are relatively prime. Let


and, for all i (1in), let yi be an integer that satisfies


Then one solution of these congruences is


Any x satisfies the set of congruences if and only if it satisfies


The Chinese remainder theoremMathworldPlanetmathPlanetmathPlanetmath originated in the book “Sun Zi Suan Jing”, or Sun Tzu’s Arithmetic Classic, by the Chinese mathematician Sun Zi, or Sun Tzu, who also wrote “Sun Zi Bing Fa”, or Sun Tzu’s The Art of War. The theorem is said to have been used to count the size of the ancient Chinese armies (i.e., the soldiers would split into groups of 3, then 5, then 7, etc, and the “leftover” soldiers from each grouping would be counted).

Title Chinese remainder theorem
Canonical name ChineseRemainderTheorem
Date of creation 2013-03-22 11:58:58
Last modified on 2013-03-22 11:58:58
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Theorem
Classification msc 11D79
Related topic ChineseRemainderTheoremInTermsOfDivisorTheory
Related topic GodelsBetaFunction