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}$.
Best Answer
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}$