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).

Examples

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.