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₁ mod m₁

x= x₂ mod m₂

.

.

.

x= x_r mod m_r

These equations have a simultaneous solution which is unique modulo m₁m₂ . . . 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 :

1. Find the common modulus, M=m₁* m₂ *. . . *m_r
2. Find M₁=M/m₁, M₂ = M/m₂, . . . , M_r = M/m_r.
3. Find the multiplicative inverse of M₁, M₂, . . . , M_r using corresponding moduli m₁,m₂, . . ., m_r. Let the inverse be M₁^-1 , M₂^-1, . . . , M_r^-1.
4. The solution is: x = (x₁ * M₁ * M₁^-1 +x₂ * M₂ *M₂^-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₁ = 3, m₂ = 5, m₃ = 7. These are pairwise prime to each other.

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

Step 2: M₁ = M/m₁ = 105 / 3 = 35.

M₂ = M/ m₂ = 105/5 = 21.

M₃ = M/ m₃ = 105/7 = 15.

Step 3: Compute the multiplicative inverse of M₁, M₂ and M₃ in moduli m₁, m₂, m₃ respectively.

M₁^-1 = 2 since (2 *35) mod 3 = 1.

M₂^-1 = 1 since (1 * 21) mod 5 = 1.

M₃^-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;
}