<s>[INST] How to find the solution of $x^2\equiv 25\pmod{32}$? I am trying to find square root of $57$ modulo $32\times 49$. For that I need to find the solutions of $x^2\equiv 57\pmod{32}$  and $x^2\equiv 57\pmod{49}$ which are $x^2\equiv 25\pmod{32}$ and $x^2\equiv 8 \pmod{49}$. Now I could find the solution of the second one as follows: $x_1=1$ is a solution to $x^2\equiv 8 \pmod{7}$. Let $x_2=x_1+7k=1+7k$ be a solution of
$x^2\equiv 8 \pmod{49}$, so
$$\begin{align*}
(1+7k)^2\equiv 8 \pmod{49}&\implies 1+14k\equiv 8\pmod{49} \\
&\implies 14k\equiv 7 \pmod{49}\\
&\implies 2k\equiv 1 \pmod{7},
\end{align*}$$ thus we can find $k$ as $4$, so $1+7k=29$ and hence $x_2=29$ is a solution of $x^2\equiv 8 \pmod{49}$.
Now for the first equation, $x_1=1$ is a solution of $x^2\equiv 25\pmod{8}$. Now I take $x_2=x_1+8k=1+8k$ to be a solution of $x^2\equiv 25 \pmod{16}$, then I try to proceed in a similar way. But I get stuck because it boils down to finding $k$ such that $2k\equiv 1\pmod{2}$ which has no solution. My question is how to find a solution for $x^2\equiv 25\pmod{32}$?
 [/INST] Let $32|x^2-25.$ Then $x$ must be odd so let $x=2n+1.$ Then
$32|(x-5)(x+5)=(2n-4)(2n+6)\;$ iff $\;8|(n-2)(n+3).$
Now one of $n-2,n+3$ is odd and the other is even so it is necessary & sufficient that $8|n-2$ or $8|n+3.$ And the rest is easy.
</s>