Back مبرهنة الباقي الصينية Arabic Teorema xinès del residu Catalan Čínská věta o zbytcích Czech Chinesischer Restsatz German Κινεζικό Θεώρημα Υπολοίπων Greek Ĉina restteoremo Esperanto Teorema chino del resto Spanish Hondarraren txinatar teorema Basque قضیه باقیمانده چینی Persian Kiinalainen jäännöslause Finnish
In mathematics, the Chinese remainder theorem 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 (no two divisors share a common factor other than 1).
For example, if we know that the remainder of n divided by 3 is 2, the remainder of n divided by 5 is 3, and the remainder of n divided by 7 is 2, then with no other information, we can determine that the remainder of n divided by 105 (the product of 3, 5, and 7) is 23. Importantly, this tells us that if n is a natural number less than 105, then 23 is the only possible value of n.
It is also known as Sunzi's theorem, as the earliest known statement is by the Chinese mathematician Sunzi in the Sunzi Suanjing in the 3rd to 5th century CE.
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 ring, with a formulation involving two-sided ideals.