Question: 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?

Answer: 
$x^2\equiv17\pmod{128}\implies x^2\equiv17\pmod{16}\equiv1$

$(4a+1)^2\equiv8a+1\pmod{16},$ 

we need $8a+1\equiv17\pmod{16}\implies a$ must be even $=2b$(say)

Again, $x^2\equiv17\pmod{128}\implies x^2\equiv17\pmod{32}$

Now $(8b+1)^2\equiv16b+1\pmod{32},$ we need $16b+1\equiv17\pmod{32}\implies b=2c+1$

$8b+1=8(2c+1)+1=16c+9$

Again, $x^2\equiv17\pmod{128}\implies x^2\equiv17\pmod{64}$

and $(16c+9)^2\equiv288c+81\pmod{64}\equiv32c+17$

For $(16c+9)^2\equiv17\pmod{64},c=2d$

$16c+9=16(2d)+9=32d+9$

Now $(32d+9)^2\equiv576d+81\equiv64d+81\pmod{128}$

We need $\displaystyle64d+81\equiv17\pmod{128}$
$\iff64d\equiv-64\pmod{128}\iff d\equiv-1\pmod2\implies d=2e-1$

$32d+9=32(2r-1)+9=64r-23\equiv-23\pmod{64}$

Similarly start with $4a-1$ to get $x\equiv23\pmod{64}$

That these are the two exclusive in-congruent solutions can be verified as follows:

$$x^2\equiv17\pmod{128}\equiv23^2$$

$$\iff128|(x-23)(x+23)$$

$$\iff32\mid\dfrac{x-23}2\cdot\dfrac{x+23}2$$

As $\dfrac{x+23}2-\dfrac{x-23}2=23$ is odd, so, they must be of opposite parity

If $32\mid\dfrac{x-23}2,x\equiv23\pmod{64}$

and $\cdots$
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$.