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}/5\) (\(\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) {
  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) {
    x += a[i] * modular_multiplicative_inverse(product / p[i], p[i]);
    x %= product;
  return x;