Calculator for the 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).
|
Input: Divisor = {3, 4, 5}, Remainder = {2, 3, 1}
Result: 11
11 is the smallest dividend such that:
(1) When we divide 11 by 3 dividieren, we get remainder 2.
(2) When we divide 11 by 4 dividieren, we get remainder 3.
(3) When we divide 11 by 5 dividieren, we get remainder 1.
2nd Example
Input: Divisor = {5, 7}, Remainder = {1, 3}
Resultat: 31
31 is the smallest divident such that:
(1) When we divide 31 by 5, we get remainder 1.
(2) When we divide 31 by 7 , we get remainder 3.
|