Understanding why we can use Chinese Remainder Theorem to Breakdown a congruence problem I am trying to understand why the procedure for solving congruence equations with the CRT works.
An example from my notes is:
$$x^2 + 1 \equiv 0 \text{ mod 10}$$
We do this problem by considering the solutions to the two congruence equations $x^2 + 1 \equiv 0 \text{ mod 2 }$ and $x^2 + 1 \equiv 0 \text{ mod 5 }$. I don't have a problem doing the rote calculation, but I'm not quite getting why this works.
Specifically, is it true that if  $x$ is a solution to $x^2 + 1 \equiv 0 \text{ mod 2}$, and $x^2 + 1 \equiv 0 \text{ mod 5}$, is it necessarily a solution to $x^2 + 1 \equiv 0 \text{ mod 10}$? I can see why the converse is true, but not this way.
Because the procedure, for example, for finding one solution to the original congruence equation is to note that $(x \equiv 1 \text{ mod 2}, x \equiv 3 \text{ mod 5)}$ is a solution to the simultaneous congruence equation: $x^2 + 1 \equiv 0 \text{ mod 2 }$ and $x^2 + 1 \equiv 0 \text{ mod 5}$. But then I don't see how we can conclude that this will be a solution to our original equation?*
*Note: I know by the CRT the simultaneous solution to $(x \equiv 1 \text{ mod 2}, x \equiv 3 \text{ mod 5)}$ is necessarily a congruence class in $\mathbb{Z}_{10}$, I just don't see how we know for certain it will satisfy the congruence equation $x^2 + 1 \equiv 0 \text{ mod 10}$.
 A: It may be easier to see when the modular arithmetic statement
is written in equivalent divisibility language:
if $2|x^2+1$ and $5|x^2+1$, then $10|x^2+1$.
A: Suppose that $\,f(x)\,$ is a polynomial with integer coef's and $\,m,n\,$ are coprime integers. By CRT, solving  $\,f(x)\equiv 0\pmod{\!mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n.\,$ By CRT, each combination of a root $\,r_i\,$ mod $\,m\,$ and a root $\,s_j\,$ mod $\,n\,$ corresponds to a unique root $\,t_{ij}\,$ mod $\,mn\,$ i.e.
$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{\!mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod{\! m}\\f(x)\equiv 0\pmod{\! n}\end{array} \\ 
&\iff&  \begin{array}{}x\equiv r_1,\ldots,r_k\pmod {\!m}\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod{\! n}\end{array}\\ 
&\iff& \left\{ \begin{array}{}x\equiv r_i\pmod{\! m}\\x\equiv s_j\pmod {\!n}\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\
&\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{\!mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\
\end{eqnarray}\qquad\qquad$$
Let's work a simple example for $\,f(x) = (x\!+\!2)(x\!+\!3)\,$ and $\,m,n = 11,17$.
$$(x\!+\!2)(x\!+\!3)\equiv 0\!\!\!\pmod{\!11\cdot 17}\iff \begin{align} x\equiv -2,-3\!\!\!\pmod{\!11}\\ x\equiv -2,-3\!\!\!\pmod{\!17}\end{align}\qquad\qquad $$
which combine to $4$ solutions $\,x\equiv (\color{#90f}{{ -2,-2}}),\,(\color{#0a0}{-3,-3}),\,(-2,-3),\,(-3,-2)\,$ mod $(11,17).\,$  By CCRT, $\bmod 187\:$  the first two yield $\,x\equiv \color{#90f}{ -2}\,$ and $\,\color{#0a0}{-3}.\,$ The third case  $\,(-2,-3)\,$ yields by CRT:
$\!\bmod\, \color{#c00}{11}\!:\,\  {-}2 \equiv\, x \equiv -3+17\,\color{#c00}k \equiv-3+6k \iff 6k\equiv1\equiv12 \iff \color{#c00}{k \equiv 2}$
therefore we infer $\ x = -3+17(\color{#c00}{2+11}n) = 31+187n,\ $ so $\ (-2,-3)\,\mapsto 31$
Finally   $\ (-3,-2) + \underbrace{(-2,-3)}_{\large31}\equiv \underbrace{(-5,-5)}_{\large -5}$ $\,\Rightarrow\,(-3,-2)\,\mapsto\, -5-31\equiv -36\ $
Hence we conclude that there are four roots $\,x \equiv \color{#90f}{-2},\, \color{#0a0}{-3},\, 31,\, -36\pmod{\!11\cdot 17}$
A: 
Claim: If $y$ is both a multiple of $2$ and multiple of $5$. then $y$ must be  a multiple of $10$.

Notice that $2$ and $5$ are coprime to each other, there exists integers $s, t$ such that $2s+5t=1$.
$$2sy+5ty=y$$
Since $2$ divides $y$, we can write $y=2k$. Since $5$ divides $y$, we can write $y=5l$.
$$2s(5l)+5t(2k)=y$$
$$10(sl+kt)=y$$
I just use the property that $2$ and $5$ are coprime. In general, if $y$ is both a multiple of $n_1$ and multiple of $n_2$ where $n_1$ and $n_2$ are coprime, then $y$ must be a multiple of $n_1n_2$
A: The explanation is very simple with the ‘abstract’ version of the Chinese remainder theorem:

Let $a,b$ be coprime integers, and $ua+vb=1$ a Bézout's relation. Then the natural map
\begin{align}
\mathbf Z&\longrightarrow \mathbf Z/a\mathbf Z\times \mathbf Z/b\mathbf Z,\\
n&\longmapsto(n\bmod a,n\bmod b),
\end{align}
is a surjective ring homomorphism with kernel the ideal $ab\mathbf Z$, hence it induces a ring isomorphism $\;\mathbf Z/ab\mathbf Z\overset{\sim}{\longrightarrow}\mathbf Z/a\mathbf Z\times\mathbf Z/b\mathbf Z$, and the inverse isomorphism  is
\begin{align}
\mathbf Z/a\mathbf Z\times\mathbf Z/b\mathbf Z &\longrightarrow \mathbf Z/ab\mathbf Z,\\
(x\bmod a,y\bmod b)&\longmapsto yua+xvb\bmod ab.
\end{align}

