Chinese Remainder Theorem

Let $p_{1}, p_{2}, \dots, p_{n}$ be distinct numbers relatively prime, for any integers $a_{1}, a_{2}, \dots, a_{n}$ there’s an integer $x$ such that

\begin{aligned} x & \equiv a_{1} (\mod p_{1}) \\ x & \equiv a_{2} (\mod p_{2}) \\ ⋮ \\ x & \equiv a_{n} (\mod p_{n}) \end{aligned}

All the solutions of this system are congruent modulo $p_{1} p_{2} \dots p_{n}$

nrich’s article on the chinese remainder illustrates the system of equations with a coordinate system in $n$ -dimensions, basically a number can represent a point in the coordinate system defined by the equation system and the point itself is a sum of unit vectors scaled by some amount

Example: Represent the number $17$ in the coordinate system defined by the integers that belong to the set of integers $Z / 5$ , $Z / 7$ and $Z / 11$ ( $Z / n$ has $n$ elements which are all the number in the range $0, 1, \dots, n - 1$ )

The statement above is equivalent to

\begin{aligned} 17 & \equiv x \equiv 2 (\mod 5) \\ 17 & \equiv x \equiv 3 (\mod 7) \\ 17 & \equiv x \equiv 6 (\mod 11) \end{aligned}

We can see that $17$ is represented by the point $(2, 3, 6)$

What we want to do is the opposite, that is find the number whose representation in the coordinate system defined by the integers that belong to the set of integers $Z / p_{1}, Z / p_{2}, \dots, Z / p_{n}$ results in the point $(a_{1}, a_{2} \dots, a_{n})$

What we can do is express these conditions as a sum of scaled unit vectors that belong to each of axis of the coordinate systems, this means that a point $(a_{1}, a_{2} \dots, a_{n})$ can be represented as

a_{1} (1, 0, 0, \dots, 0) + a_{2} (0, 1, 0, 0, \dots, 0) + \dots + a_{n} (0, 0, \dots, 0, 1) = (a_{1}, a_{2}, \dots, a_{n})

If we represent each point as $x_{i}$

\begin{matrix} (1) & a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = (a_{1}, a_{2}, \dots, a_{n}) \end{matrix}

Let’s take the first term of the sum, $x_{1}$ is a number which must fulfill the following equivalences for each axis of the coordinate system

\begin{aligned} x_{1} & \equiv 1 (\mod p_{1}) \\ x_{1} & \equiv 0 (\mod p_{2}) \\ ⋮ \\ x_{1} & \equiv 0 (\mod p_{n}) \end{aligned}

From the system of equations above we can see that $x_{1} ∣ p_{2} p_{3} \dots p_{n}$ which means that $x_{1}$ is some multiple of the multiplication i.e. $x_{1}^{'} = p_{2} p_{3} \dots p_{n} \cdot x_{1}$

p_{2} p_{3} \dots p_{n} \cdot x_{1} \equiv 1 (\mod p_{1})

Given the fact that $p_{2} p_{3} \dots p_{n}$ is relatively prime to $p_{1}$ the product has a modular multiplicative inverse which can be found using the extended euclidean algorithm, in fact we have to solve $n$ of this equations each having the form

\frac{p_{1} p_{2} \dots p_{n}}{p_{i}} \cdot x_{i} \equiv 1 (\mod p_{i})

Finally we have to plug these values into the equation $(1)$

/**
 * Computes the value of `x` for the linear congruent system of equations
 *
 *    x ≡ a_1 (mod p_1)
 *    x ≡ a_2 (mod p_2)
 *      |
 *    x ≡ a_n (mod p_n)
 *
 * All the solutions are given by the expression `x + k · p_1p_2...p_n`
 * where `k` is an integer
 *
 * @param {vector<int>} a
 * @param {vector<int>} p
 * @return {int} A solution for the system if it exists
 */
int chinese_remainder(vector<int> &a, vector<int> &p) {
  int x = 0;
  int product = 1;
  for (int i = 0; i < p.size(); i += 1) {
    product *= p[i];
  }
  for (int i = 0; i < a.size(); i += 1) {
    int k = product / p[i];
    x += a[i] * modular_multiplicative_inverse(k, p[i]) * k;
    x %= product;
  }
  return x;
}

See Also

Integer Factorization

Divisor Function

Primality Test