## Chinese remainder theorem |

The **Chinese remainder theorem** is a theorem of *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

The earliest known statement of the theorem is by the Chinese mathematician * 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

- history
- theorem statement
- proof
- computation
- over principal ideal domains
- over univariate polynomial rings and euclidean domains
- generalization to non-coprime moduli
- generalization to arbitrary rings
- applications
- see also
- notes
- references
- further reading
- external links

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:

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 ^{[4]} Special cases of the Chinese remainder theorem were also known to ^{[5]} The result was later generalized with a complete solution called *Dayanshu* (大衍術) in * Mathematical Treatise in Nine Sections* (數書九章,

The notion of congruences was first introduced and used by *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 ^{[10]}