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