Chinese Remainder Theorem

We have Two arrays ans[0,1,----(n-1)] and rem[0,1,----(n-1)]. We have to find minimum value of x such that

x%ans[0] = rem[0], x%ans[1] = rem[1], and so on.

Chinese Remainder Theorem states that there always exist x which satisfy the given congruence

To find the value of x we have Two approaches. The first approach is to iterate through the loop and check the value of x. This approach lack when the value of x is very very large.

The second approach is to use the concept of inverse modular exponentiation.

The second solution is based on the formula below

x = (Σ(rem[i]*p[i]*inv[i]))%prod

we have already defined the array rem. prod is the product of all the numbers in the array ans. prod = ans[0]ans[1]...........*ans[n-1]

p[i] is actually prod divided by numbers in an array. p[i] = prod/ans[i]

inv[i] is the modular inverse of p[i] with the respect to the ans[i]

Let's take the example ans[] = {3,4,5} and rem[]={2,3,1} For these two array,prod = 3x4x5 = 60 p[]={20,15,12} and inv[] = {2,3,3}

Now x = rem[0]*p[0]*inv[0] + rem[1]*p[1]*inv[1] + rem[2]*p[2]*inv[2] = 2x20x2 + 3x15x3 + 1x12x3 = 80 + 135 + 36 = 251

x =x%60 = 251%60 = 11

For x = 11, It satisfies the congruence.

For Modular Inverse, Below is the code

int inv(int a, int m)
{
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1)
    return 0;

    // Apply extended Euclid Algorithm
    while (a > 1)
    {

        q = a / m;

        t = m;


        m = a % m, a = t;

        t = x0;

        x0 = x1 - q * x0;

        x1 = t;
    }


    if (x1 < 0)
    x1 += m0;

    return x1;
}

The below code is how we compute the formula and return the minimum value of x.

int findMinx(int num[],int rem[],int n)
{
    int prod = 1;
    for(int i=0;i<n;i++)
    {
        prod *= num[i];
    }
    ll results = 0;
    for(int i=0;i<n;i++)
    {
        int pp = prod/num[i];
        int inverse = inv(pp,num[i]);
        results += (rem[i]*pp*inverse);

    }
    return results%prod;
}

Driver Code

int num[] = {4,7,8};
int rem[] = {6,7,2};
int n = sizeof(num)/sizeof(num[0]);

cout<<findMinx(num,rem,n);

If you like this article, share it with your friends and I will see you in the next one.