Chinese Remainder Theorem was discovered by the Chinese mathematician Sun-Tsu in around 100 AD.

It is used to solve a set of congruent equations with a single variable but different moduli, which are relatively prime.

Let us consider such a set of equations:

x = x1 mod m1

x= x2 mod m2

.

.

.

x= xr mod mr

These equations have a simultaneous solution which is unique modulo m1m2 . . . mr. In this theorem , m1,m2, . . . ,mr should be pairwise relatively prime is essential. if this condition be not satisfied there may not exist a solution of the system of congruences.

The solution can be obtained by performing the following steps.

Steps :

1. Find the common modulus, M=m1* m2 *. . . *mr
2. Find M1=M/m1, M2 = M/m2, . . . , Mr = M/mr.
3. Find the multiplicative inverse of M1, M2, . . . , Mr using corresponding moduli m1,m2, . . ., mr. Let the inverse be M1-1 , M2-1, . . . , Mr-1.
4. The solution is: x = (x1 * M1 * M1-1 +x2 * M2 *M2-1 + . . . + xr * Mr * Mr-1) mod M.

Example:

Q: Solve the system of linear congruences

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

Solution:

Given m1 = 3, m2 = 5, m3 = 7. These are pairwise prime to each other.

Step 1: Compute M = 3 * 5 * 7 = 105

Step 2: M1 = M/m1 = 105 / 3 = 35.

M2 = M/ m2 = 105/5 = 21.

M3 = M/ m3 = 105/7 = 15.

Step 3: Compute the multiplicative inverse of M1, M2 and M3 in moduli m1, m2, m3 respectively.

M1-1 = 2 since (2 *35) mod 3 = 1.

M2-1 = 1 since (1 * 21) mod 5 = 1.

M3-1 = 1 since (1 * 15) mod 7 = 1.

Step 4:

x = ( 1 * 35 * 2 + 2 * 21 * 1 + 3 * 15 * 1) mod 105 = 157 mod 105

x= 52 mod 105.

Below is the implementation in c.

``````#include <stdio.h>

int mul_inv(int a, int b)
{
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1){
return 1;
}
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0){
x1 = x1+ b0;
}
return x1;
}
int chinese_remainder(int *m, int *x, int len)
{
int p, i, M = 1, sum = 0;

for (i = 0; i < len; i++){
M = M*m[i];
}

for (i = 0; i < len; i++) {
p = M / m[i];
sum += x[i] * mul_inv(p, m[i]) * p;
}

return sum % M;
}
int main()
{
int m[] = { 3,5,7};
int x[] = { 1,2,3};
printf("%d\n", chinese_remainder(m, x, sizeof(m)/sizeof(m[0])));
return 0;
}``````