### Chinese Remainder Theorem

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 =_{ }x_{1} mod m_{1}

x= x_{2} mod m_{2}

.

.

.

x= x_{r} mod m_{r}

These equations have a simultaneous solution which is unique modulo m_{1}m_{2} . . . m_{r}. 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 :**

- Find the common modulus, M=m
_{1}* m_{2}*. . . *m_{r} - Find M
_{1}=M/m_{1}, M_{2}= M/m_{2}, . . . , M_{r}= M/m_{r}. - Find the multiplicative inverse of M
_{1}, M_{2}, . . . , M_{r}using corresponding moduli m_{1},m_{2}, . . ., m_{r}. Let the inverse be M_{1}^{-1}, M_{2}^{-1}, . . . , M_{r}^{-1}. - The solution is: x = (x
_{1}* M_{1}* M_{1}^{-1}+x_{2}* M_{2}*M_{2}^{-1}+ . . . + x_{r}* M_{r}* M_{r}^{-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 m_{1} = 3, m_{2} = 5, m_{3} = 7. These are pairwise prime to each other.

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

**Step 2:** M_{1 }= M/m_{1} = 105 / 3 = 35.

M_{2} = M/ m_{2} = 105/5 = 21.

M_{3} = M/ m_{3} = 105/7 = 15.

**Step 3:** Compute the multiplicative inverse of M_{1}, M_{2} and M_{3} in moduli m_{1}, m_{2}, m_{3} respectively.

M_{1}^{-1} = 2 since (2 *35) mod 3 = 1.

M_{2}^{-1} = 1 since (1 * 21) mod 5 = 1.

M_{3}^{-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;
}
```