Chinese remainder theorem

Sunzi's original formulation: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) with the solution x = 23 + 105k where k ∈ ℤ

The Chinese remainder theorem is a theorem of number theory, which states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

The earliest known statement of the theorem is by the Chinese mathematician Sunzi in Sunzi Suanjing in the 3rd century AD.

The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.

The Chinese remainder theorem (expressed in terms of congruences) is true over every principal ideal domain. It has been generalized to any commutative ring, with a formulation involving ideals.

History

The earliest known statement of the theorem, as a problem with specific numbers, appears in the 3rd-century book Sunzi Suanjing by the Chinese mathematician Sunzi:[1]

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?[2]

Sunzi's work contains neither a proof nor a full algorithm.[3] What amounts to an algorithm for solving this problem was described by Aryabhata (6th century).[4] Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).[5] The result was later generalized with a complete solution called Dayanshu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections (數書九章, Shushu Jiuzhang).[6]

The Chinese remainder theorem appears in Gauss's 1801 book Disquisitiones Arithmeticae.[7]

The notion of congruences was first introduced and used by Gauss in his Disquisitiones Arithmeticae of 1801.[8] Gauss illustrates the Chinese remainder theorem on a problem involving calendars, namely, "to find the years that have a certain period number with respect to the solar and lunar cycle and the Roman indiction."[9] Gauss introduces a procedure for solving the problem that had already been used by Euler but was in fact an ancient method that had appeared several times.[10]