<s>[INST] Solving $x^2=17\pmod{128}$ I'm attempring to solve a congruence $x^2 \equiv 17\pmod{128}$ but not quite sure how to go about it. I see that $128 = 2^7$, but the Chinese Remainder Theorem doesn't apply to $\gcd > 1$. I found one solution quite easily by finding solutiong to $x^2 \equiv\pmod{32}$ which was $x \equiv 23\pmod{32}$ and it turned out that $23 + 128x_0 \equiv 17\pmod{128}$. How do I find the other solution ans what's the proper way of doing it?
 [/INST] The  series for  the square root is
\begin{eqnarray}
\sqrt{1+16 t} =1 + 8 t - 32 t^2 + 256 t^3 - 2560 t^4 + 28672 t^5 - 344064 t^6+\\ + 
4325376 t^7 - 56229888 t^8 + 749731840 t^9 - 10196353024 t^{10}+ \cdots
\end{eqnarray}
The first three terms truncation $1 + 8 t - 32t^2$ has square $1 + 16 t - 512 t^3 + 1024 t^4$. Therefore, for $t=1$ we obtain
$$(1+8-32)^2 = 17 -512 + 1024= 17 + 512 \equiv 17 \!\!\!\!\mod 512$$
therefore, $23^2 \equiv 17 \!\!\!\!\mod 128$.
Let $x$ any other solution of $x^2 \equiv 17 \!\!\!\!\mod 128$. Then 
$y\colon =\frac{x}{23} \!\!\!\mod 128$ satisfies $y^2\equiv 1 \!\!\!\mod 128$
and for this we have $4$ solutions $\pm 1$, $\pm 65  \!\!\!\mod 128$. 
Therefore, the solutions are $\pm 23$, $\pm 23 \cdot 65 \!\!\!\mod 128$, that is 
$$23, 41, 87, 105$$
</s>