Community hub
Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Chinese remainder theorem
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).
The theorem is sometimes called Sunzi's theorem. Both names of the theorem refer to its earliest known statement that appeared in Sunzi Suanjing, a Chinese manuscript written during the 3rd to 5th century CE. This first statement was restricted to the following example:
If one knows 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, one can determine the remainder of n divided by 105 (the product of 3, 5, and 7) without knowing the value of n. In this example, the remainder is 23. Moreover, this remainder is the only possible positive value of n that is less than 105.
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.
The earliest known statement of the problem appears in the 5th-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?
Sunzi's work would not be considered a theorem by modern standards; it only gives one particular problem, without showing how to solve it, much less any proof about the general case or a general algorithm for solving it. An algorithm for solving this problem was described by Aryabhata (6th century). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century) and appear in Fibonacci's Liber Abaci (1202). The result was later generalized with a complete solution called Da-yan-shu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections which was translated into English in early 19th century by British missionary Alexander Wylie.
Hub AI
Chinese remainder theorem AI simulator
(@Chinese remainder theorem_simulator)
Chinese remainder theorem
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).
The theorem is sometimes called Sunzi's theorem. Both names of the theorem refer to its earliest known statement that appeared in Sunzi Suanjing, a Chinese manuscript written during the 3rd to 5th century CE. This first statement was restricted to the following example:
If one knows 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, one can determine the remainder of n divided by 105 (the product of 3, 5, and 7) without knowing the value of n. In this example, the remainder is 23. Moreover, this remainder is the only possible positive value of n that is less than 105.
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.
The earliest known statement of the problem appears in the 5th-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?
Sunzi's work would not be considered a theorem by modern standards; it only gives one particular problem, without showing how to solve it, much less any proof about the general case or a general algorithm for solving it. An algorithm for solving this problem was described by Aryabhata (6th century). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century) and appear in Fibonacci's Liber Abaci (1202). The result was later generalized with a complete solution called Da-yan-shu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections which was translated into English in early 19th century by British missionary Alexander Wylie.