Solving $x^2=17\pmod{128}$

$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$

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}$.

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$

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$$