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