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 = 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;
}