Find all the square roots of $11$ in $\mathbb Z_{35}$ by CRT.

Question

I understand what the Chinese remainder theorem is. However I am not sure how to apply it to my question. Can someone explain please?

Answer 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.

$$\begin{align}&\overbrace{{\rm mod}\ 5\!:\,\ x^2\equiv 11\equiv 1}^{5\mid (x-1)(x+1)\iff \color{#0a0}{5\mid x-1}\ {\rm or}\ \color{#0a0}{5\mid x+1}\!\!\!\!\!\!\!\!\!\!}\!\iff \color{#0a0}{x\equiv \pm1}\equiv: \color{#0af}{a}\\[.2em] &{\rm mod}\ 7\!:\,\ x^2\equiv 11\equiv 4\iff x\equiv \pm 2\equiv: \color{#0af}{b}\end{align}\qquad\qquad$$

---

Next we solve the system $\, x\equiv \color{#0af}a\pmod{\! 5}\,$ and $\,x\equiv \color{#0af}b\pmod{\! 7}\,$ for $\rm\color{#0af}{generic}$ (any) $\rm\color{#0af}{a,b}$

${\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 \color{#0a0}1, 2\,$ yields that $\, x = 2 + 14(2\!-\!1) = 16+35n$

Its negation $\,{-}16\equiv 19\pmod{\!35}\,$ is also a square root (case $\,a,b \equiv -1,-2 \equiv -[1,2])$

Do similarly for $\,a,b \equiv \color{#0af}{-1,2}\,$ and its negative $\,1,-2\,$ to get all $\,4\,$ square roots, yielding

$$ (x\!-\!16)(x\!+\!16) \equiv x^2\!-\!11\equiv (x^2\!-\!\color{#0af}9)(x^2\!+\!9)\pmod{\!35}\qquad$$

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\,$ both $\!\bmod m\,$ and $\!\bmod n.\,$ By CRT, each combination of a root $\,r_i\bmod m\,$ and a root $\,s_j\bmod n\,$ corresponds to a unique root $\,t_{ij}\bmod mn\,$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{\!mn}\!\!&\overset{\small\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{\small\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\qquad$$