Chinese Remainder Theorem - Ground Plan of Existence Proof Let $n_{1},\ n_{2},\ n_{3},\ \cdots,\ n_{r}$ be positive integers such that
$\gcd(n_{i}, n_{j})=1$ for $1 \le \quad i\neq j \quad \le r$
Then the simultaneous linear congruences $ x\equiv a_i \pmod {n_i} $ for all $1 \le i \le r$ has a solution satisfying all these equations. Moreover the solution is unique modulo
$n_1 n_2 n_3 \cdots n_r$.
Proof of Existence. I skip proof of uniqueness. Let $n=n_{1}n_{2}n_{3}\cdots n_{r}$. For each integer $k=1,2,3,\ \cdots,\ r$, let $N_{k} =n_{1}n_{2}n_{3}\cdots n_{k-1}n_{k+1}\cdots n_{r}$ = the product of all the moduli $n_{i}$ with the modulus $n_{k}$ missing. 

(1) How can you prefigure to consider this, to start the proof? This product is uncanny?

We are given that $\gcd(n_i, n_j)=1$ for $i\neq j$.  By reason of $\gcd(a,b) = \gcd(a,c) =1,$ then $\gcd(a, bc) = 1$.  Thence $\gcd(N_k, n_k ) = 1$.
Consider if the linear congruence $N_k x\equiv 1 \pmod{n_k}$ has any solutions.

(2) Where does $N_{k}x\equiv 1 \pmod{n_k}$ hail from? How can you prefigure to consider this?

Since $\gcd(N_k, n_k) = 1$, thence by reason of the Linear Congruence Theorem, the linear congruence $N_{k}x\equiv 1 \pmod {n_k}$ has a unique solution. Dub it $x_k$, thence $$ \color{magenta}{ N_k x_k \equiv 1\pmod{n_k}. \tag{♯} }$$
We construct a solution which satisfies all the given simultaneous linear congruences:
$$
x^* =a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 +\cdots + a_r N_r x_r
$$

(3) Where does this construction hail from? Can you calculate this? 

Let us see if this satisfies the first given linear congruence $ x\equiv a_1 \pmod {n_1} $.
By the above definition of $N_{2},\ N_{3},\ N_{4}, \ldots, N_{r}$ these numbers are multiplies of $n_{1}$.
Therefore $ a_{2}N_{2}x_{2}\equiv 0\pmod {n_1}, a_{3}N_{3}x_{3}\equiv 0 \pmod {n_1} \cdot,\ a_{r}N_{r}x_{r}\equiv 0 \pmod {n_1} $,
Thence if I take $x^*$ to modulus $n_1$, then by cause of $\color{magenta}{(♯)}$
$$\begin{align} x^*  & \equiv a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+a_{3}N_{3}x_{3}+\cdots+a_{r}N_{r}x_{r} \pmod {n_1} \\
& \equiv  a_{1} \color{magenta}{ N_{1}x_{1} }+0+0+\cdots+0 \\
& \equiv a_{1} \color{magenta}{ 1 } \pmod {n_1}
\end{align}$$
Hence $x^*$ satisfies the first simultaneous congruence $x\equiv a_1 \pmod {n_1}$. Similarly we can show that the solution constructed satisfies the remaining congruences.
 A: (1) I agree that the product is not that natural at first sight, and maybe someone will give an intuitive or better interpretation, but here is how I see the proof strategy with an analogy of linear algebra : we try to build the $x^{*}$ that verifies the conditions $x^{*} \equiv a_i \mod{n_i}$. Somehow, these conditions can be seen as "projection" equations : when we take the congruence modulo one of the $n_k$s, we need to satisfy a given equation. The hypothesis on the $gcd$s would be a "freedom" hypothesis in a vector space. Once you see the problem like this, this is natural to try to build something similar to a basis (ie coordinates system), such that we can set easily the wanted values $x^{*} \mod{n_k}$ independently.
The product is the first step toward this goal. We know that the product of all $n_k$ is obviously zero modulo any $n_k$, but by removing one, you build a number $N_k$ that is zero modulo any $n_i$ EXCEPT $n_k$ (because of relative primality, it is even invertible modulo $n_k$). You can find some similar constructions e.g. in Lagrange interpolation, when you build very similarly polynomials $L_k$ that are null at any $b_i$ (where $b_i$ are given real numbers) except $b_k$, and there are several other examples. Here, these $N_k$ act as filters, selecting only one value when taking the modulo $n_k$. Well, that's interesting, because if you take a linear combination of these numbers, you can indeed do something like a decomposition on a basis : let $$y=\sum_{i=1}^{r} a_i N_i$$ , then you can do a "projection" and check that : $$y \equiv a_i N_i \mod{n_i}$$
But you don't know $N_i$'s value modulo $n_i$, and you are not already done. You would like to get rid of this annoying $N_i$'s value :
(2) We do something like a normalization. If we could transform $N_i$'s to a new "basis" $N'_i$ such that $$N'_i \equiv 1 \mod {n_i}$$, this would be perfect. This is exactly what is done : the $gcd$'s hypothesis allow you to find an inverse $x_i$ for $N_i \mod {a_i}$, and doing the multiplication, you get a new "unitary basis" $N'_i = x_i N_i$. Once again, you do quite the same than with Lagrange polynomials, when dividing by $X-b_k$ in $L_k=\frac{\prod_{i \neq k}(X-b_i)}{X-b_k}$ such that $L_k(b_k)=1$. Now you just have to :
(3) Build your solution by decomposing it on the new "coordinate system" you just elaborated $$x^{*} = \sum_{i=1}^{r} a_i N'_i$$
You can indeed calculate this, because the inverse $x_i$ you have to find in (2) is given by the extended Euclid algorithm (that gives the bezout coefficients $u,v$ such that $u n_i + v N_i = 1$, then taking the congruence you see that in fact $v \mod{n_i}$ is a solution). Once you have $x_k$, since you have $n_k$ and $a_k$, nothing prevents you from practically compute $x^{*}$.
