Chinese Remainder Theorem

Problem introduction

The Chinese Remainder theorem is used to solve problems typical of the form “Find a number which when divided by 2 leaves remainder 1, when divided by 3 leaves remainder 2, and when divided by 7 leaves remainder 5”. These problems can be reformulated into a system of linear congruence and can then be solved using the Chinese Remainder theorem. For example, the above problem can be expressed as a system of three linear congruences:

x ≡ 1 (mod 2), x ≡ 2 mod(3), x ≡ 5 mod (7)

We are given with two arrays, i.e., num[] and rem[]. For the above example, we can have num[] = {2, 3, 7} and rem[] = {1, 2, 5}. The Chinese Remainder theorem states that there always exists an x that satisfies given congruence. Basically, we are given k numbers which are pairwise co-prime and given remainders of these numbers when an unknown number x is divided by them. We need to find the minimum possible value of x that produces given remainders. In other words, we can say that there exists a value of x for the below relations:

x % num[0] = rem[0],
x % num[1] = rem[1],
.......................
x % num[k-1] = rem[k-1]

Solution

A naive approach is to find x is to start with 1 and one by one increment it and check if it is divisible with given elements in num[] and if it produces corresponding remainders in rem[]. Once we find such an x, we get our solution.

But obviously, the naive approach would have a large time complexity if the numbers are more. So, according to the Chinese Remainder theorem

x = $\sum_{0<=i<=(n-1)}^n$ (rem[i] * pp[i] * inv[i])) % prod

where

• rem[i] is the given array of remainders
• prod is the product of all given numbers
• prod = num[0] * num[1] * ... * num[k-1]
• pp[i] is product of all except for num[i]
• pp[i] = prod / num[i]
• inv[i] = Modular Multiplicative Inverse of pp[i] with respect to num[i]