Let $p_1, p_2, \ldots, p_n$ be distinct numbers relatively prime, for any integers $a_1, a_2, \ldots, a_n$ there’s an integer $x$ such that

$$ \begin{align*} x &\equiv a_1 \pmod{p_1} \\ x &\equiv a_2 \pmod{p_2} \\ & \; \vdots \\ x &\equiv a_n \pmod{p_n} \\ \end{align*} $$

All the solutions of this system are congruent modulo $p_1p_2 \ldots 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 $\mathbb{Z}/5$, $\mathbb{Z}/7$ and $\mathbb{Z}/11$ ($\mathbb{Z}/n$ has $n$ elements which are all the number in the range $0, 1, \ldots, n - 1$)

The statement above is equivalent to

$$ \begin{align*} 17 &\equiv x \equiv 2 \pmod{5} \\ 17 &\equiv x \equiv 3 \pmod{7} \\ 17 &\equiv x \equiv 6 \pmod{11} \end{align*} $$

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 $\mathbb{Z}/p_1, \mathbb{Z}/p_2, \ldots, \mathbb{Z}/p_n$ results in the point $(a_1, a_2 \ldots, 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 \ldots, a_n)$ can be represented as

$$ a_1(1, 0, 0, \ldots, 0) + a_2(0, 1, 0, 0, \ldots, 0) + \ldots + a_n(0, 0, \ldots, 0, 1) = (a_1, a_2, \ldots, a_n) $$

If we represent each point as $x_i$

$$ \begin{equation}\label{chinese-remainder-as-points} a_1x_1 + a_2x_2 + \ldots + a_nx_n = (a_1, a_2, \ldots, a_n) \end{equation} $$

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{align*} x_1 &\equiv 1 \pmod{p_1} \\ x_1 &\equiv 0 \pmod{p_2} \\ & \vdots \\ x_1 &\equiv 0 \pmod{p_n} \\ \end{align*} $$

From the system of equations above we can see that $x_1 \mid p_2p_3 \ldots p_n$ which means that $x_1$ is some multiple of the multiplication i.e. $x_1’ = p_2p_3 \ldots p_n \cdot x_1$

$$ p_2p_3 \ldots p_n \cdot x_1 \equiv 1 \pmod{p_1} $$

Given the fact that $p_2p_3 \ldots 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_1p_2 \ldots p_n}{p_i} \cdot x_i \equiv 1 \pmod{p_i} $$

Finally we have to plug these values into the equation \eqref{chinese-remainder-as-points}

/**
 * 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;
}