Quadratic Residue Question

Question

I'm trying to understand how having a quadratic residue $x \mod m$, where $m = a_1 a_2 \cdots a_n$, implies there is also a quadratic root $y\mod a_i$, where $a_i$ is a factor of $m$. My textbook doesn't really go into much detail, saying that the proof follows easily, so I suspect there must be some really simple reason for it. Any help? How can I take a quadratic residue $x \mod m$ and get one $x \mod a_i$?

Answer 1

Hint: recall that a congruence persists $\!\bmod \rm\color{#c00}{factors}$ of the modulus, hence

$$ a^2\equiv b\!\!\!\pmod{\!\color{#c00}mn} \,\Rightarrow\, a^2\equiv b\!\!\!\pmod{\!\color{#c00}m}\qquad$$

More generally roots of polynomial $\,f(x)\,$ (with integer coef's) persist in the same way, i.e.

$$f(a)\equiv 0\!\!\!\pmod{\!\color{#c00}mn}\,\Rightarrow\, f(a)\equiv 0\!\!\!\pmod{\!\color{#c00}m}\qquad$$

so the first inference is the special case $\,f(x) = x^2 - b,\,$ i.e. persistence of square roots (in algebra we call $\,a\,$ a square-root of $\,b\,$ iff $\,a^2 \equiv b\:\!$; beware that there can be more than two square roots, e.g. $\!\bmod 8\!:\ a^2\equiv 1\iff \,a\equiv 1,3,5,7\equiv \pm1,\pm3,\, $ and, as above, they persist $\!\bmod 4\,$ as $\,\pm1)$.