How do I use the Chinese remainder theorem to find all the square roots of 11 in $\mathbb Z_{35}$?

Solution 1:

We apply CRT as explained in the Remark below: first we compute the square roots $\!\bmod 5\ \&\ 7$ then we take all possible combinations of roots and lift them to roots $\bmod 35\,$ using CRT.

${\rm mod}\ 5\!:\,\ x^2\equiv 11\equiv 1\iff x\equiv \pm1\equiv: a$

${\rm mod}\ 7\!:\,\ x^2\equiv 11\equiv 4\iff x\equiv \pm 2\equiv: b.\ $

Next we solve by CRT the generic system $\, x\equiv a\pmod 5\,$ and $\,x\equiv b\pmod 7$

${\rm mod}\ 5\!:\ a \equiv x\equiv b+7\color{#c00}k\equiv b+2k\iff 2k\equiv a\!-\!b\!\overset{\times\,(-2)}\iff \color{#c00}{k\equiv 2(b\!-\!a)}$

therefore $\ x = b+7\color{#c00}k = b+7(\color{#c00}{2(b\!-\!a)+5n}) = b+14(b\!-\!a)+35n$

For example the case $\, a,b \equiv 1, 2\,$ yields that $\, x = 2 + 14(2\!-\!1) = 16+35n$

Its negation $\,-16\equiv 19\pmod{\!35}\,$ is also a square root - the case $\,a,b \equiv -1,-2$.

Do similarly for $\,a,b \equiv -1,2\,$ and its negative $\,1,-2\,$ to get all $4$ square roots (per below).

Remark $\ $ If $\,m,n\,$ are coprime then, by CRT, solving a polynomial $\,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$$