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?
 A: Outline: Let $a$ be a particular solution of $x^2\equiv 17\pmod{128}$. Let $x$ be any solution. Then there is a unique $y$ (modulo $128$) such that $x\equiv ay\pmod{128}$. 
We have $(ay)^2\equiv 17\pmod{128}$ if and only if $y^2\equiv 1\pmod{128}$. So we need to find all solutions $y$ of this congruence. 
That may have been done in your course already. If $n\ge 3$, then the congruence $y^2\equiv 1\pmod{2^n}$ has exactly $4$ solutions,  namely $y\equiv \pm 1\pmod{2^n}$ and $y\equiv \pm (1+2^{n-1})\pmod{2^n}$.
A: Let $x$ and $y$ be relatively prime with $128$. If $x^2=y^2$ then $(xy^{-1})^2=1$ so $xy^{-1}=\pm1 \iff x=\pm y$, this tells us the number of solutions is two or zero, lets look for the solutions in this case.
It is a somewhat well-know result that $5$ generates half of $\mathbb Z_{2^n}^{\cdot}$. So lets look at the powers of $5\bmod 128$:
$1,
5,
25,
125,
113,
53,
9,
45,
97,
101,
121,
93,
81,
21,
105,
13,
65,
69,
89,
61,
49,
117,
73,
109,
33,
37,
57,
29,
17$
Oh, from the looks of it $5^{28}\equiv 17\bmod 128$. Therefore $(5^{14})^2\equiv 17\bmod 128$.
So our solutions are $5^{14}$ and $-(5^{14})$, according to our previous calculations $5^{14}\equiv 105$. So the solutions are $105$ and $23$
A: 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$$
A: We have to solve $x^2\equiv 17 \pmod{128}$
Now,$128=2^7$
So,we are to solve an equation of the form $x^2\equiv a\pmod {2^\alpha}$
We follow the ascending method:
First we find a root of $x^2\equiv 17 \pmod{16}$ which is $x^2\equiv 1\pmod{16}$
We can see that $x_4=1$ is a solution to the given equation.
Now the ascending method says that if $x_i$ is a solution of $x^2\equiv a \pmod{2^i}$,then a solution of $x^2\equiv a\pmod{2^{i+1}}$ is $x_{i+1}=x_i+2^{i-1}k$
Putting this solution in the equation,we can find a value of $k$.
Hence we can find $x_{i+1}$.
Using this method it is easy to see that $x_4=1,x_5=9,x_6=9,x_7=41$.
Now,the square roots of $1$ modulo $128$ are $\pm1,2^{7-1}\pm1$ .So multiplying by $41$ we get all the solutions of $x^2\equiv 17 \pmod{128}$ as $41,87,105,23$.
