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}$?
Best Answer
Well, the easiest way to find a solution of $x^2\equiv 25\pmod{32}$ is to observe that $25$ is a perfect square, so $5^2=25$ which means that certainly $5^2\equiv 25\pmod{32}$ as well. If it holds in the good old integers, it certainly holds mod whatever.
You quickly earn another solution for free: $(-5)^2 \equiv 27^2 \equiv 25\pmod{32}$ as well. As you’ve observed, a simple Hensel-style lifting doesn’t work mod powers of $2$, but you can easily check that adding (or subtracting) $16$ to each of those solutions yields another one. Thus $11$ and $21$ are two other residues mod $32$ whose squares are congruent to $25$. Indeed, $(a+16)^2 \equiv a^2+32a+16^2 \equiv a^2\pmod{32}$.