Chinese Remainder Theorem | Mathematics

We are given two sets of integers such that the elements in Set-1 divides a number ‘x’ and leaves the remainder equal to the element present in the corresponding position in Set-2.

x % num[1] = rem[1]

x % num[2] = rem[2]

x % num[3] = rem[3]

. . . . . . . . . . . . . . . .

x % num[n] = rem[n]

Here,

Set-1 = {num[1], num[2], num[3], . . . , num[n]}

Set-2 = {rem[1], rem[2], rem[3], . . . , rem[n]}

All the numbers present in Set 1 are pairwise co-prime, which also means that gcd of any of the pair of numbers in Set-1 is 1.

Chinese Remainder Theorem states that there always exists a value of x for which the above congruences holds true.

Input:  num[] = {5, 7}, rem[] = {1, 3}
Output: 31
Here value of x came out to be 31.
Explanation: 
31 is the smallest number such that:
  (1) When we divide it by 5, we get remainder 1. 
  (2) When we divide it by 7, we get remainder 3.

Input:  num[] = {3, 4, 5}, rem[] = {2, 3, 1}
Output: 11
Here value of x came out to be 11.
Explanation: 
11 is the smallest number such that:
  (1) When we divide it by 3, we get remainder 2. 
  (2) When we divide it by 4, we get remainder 3.
  (3) When we divide it by 5, we get remainder 1.

Furthermore, it states that all the solutions of x are congruent modulo of the product of the numbers present in Set 1.

In the above first example, we got x = 31. The least value of x for which the congruences hold true is 31, but, there exists other values of x for which the congruence holds true, which can be described by:

x = a + m*n
Here,
a = least value of x for which congruence holds true
m = positive integer (>=0)
n = product of the numbers, present in Set 1 ({num[1] x num[2] x num[3] x . . . x num[n]})

Putting the values, taking m = 1,
x = 31 + 1*(5*7)
x = 31 + 35
x = 66
Verification:
66 % 5 = 1
66 % 7 = 3

A Naïve Approach to this problem is to check for all values of x, starting from 1, and checking for the congruence of that value by dividing it with elements in Set-1 and equating with elements in Set-2.

#include<bits/stdc++.h>
using namespace std;
 
int findMinX(int num[], int rem[], int k)
{
    int x = 1;
 
    while (true)
    {
        int j;
        for (j=0; j<k; j++ )
            if (x%num[j] != rem[j])
               break;
 
        if (j == k)
            return x;
 
        x++;
    }
 
    return x;
}
 
int main(void)
{
    int num[] = {3, 4, 5};
    int rem[] = {2, 3, 1};
    int k = sizeof(num)/sizeof(num[0]);
    cout << "x is " << findMinX(num, rem, k);
    return 0;
}

Output: x is 11

Time Complexity  : O(N), N is the product of all elements of num[] array.

Auxiliary Space : O(1)

An efficient approach to this problem is to use Inverse Modulo Based Implementation, which uses Extended Euclidean Algorithm to Compute the Value of x.