I'm trying to find a proof that $ 17 $ is a square residue $ \pmod{2^k} $ for all positive integers $ k $. I know some very general theorems such as the Quadratic Reprocity Law, but they work only for primes.
I could also use Hensel's lemma for the polynomial $ f = x^2 - 17 $, but it doesn't hold true that $ f' \neq 0 \pmod{2} $.
I would appreciate a hint
On
We use a counting argument. Let $k\ge 3$. Note that on the odd numbers between $1$ and $2^k-1$, the function $x^2$ (modulo $2^k$) is $4$ to $1$. This is because the congruence $w^2\equiv 1\pmod{2^k}$ has precisely $4$ solutions, $w\equiv \pm 1\pmod{2^k}$ and $w\equiv 2^{k-1}\pm 1\pmod{2^k}$. So one-quarter of the odd numbers between $1$ and $2^k-1$ are in the range of the squaring function modulo $2^k$.
The square of an odd number is congruent to $1$ modulo $8$. So no number of the form $8q+3$, $8q+5$, or $8q+7$ is in the range of the squaring function. It follows that every number of the form $8q+1$ is in that range.
In order to prove that $17$ is a quadratic residue $\pmod{2^k}$, it is sufficient to show that: $$ 17^{2^{k-2}}\equiv 1\pmod{2^k} \tag{1}$$ but that trivially holds by induction on $k$, since:
$$ \nu_2\left(17^{2^{n+1}}-1\right) = \nu_2\left(17^{2^{n}}+1\right)+\nu_2\left(17^{2^{n}}-1\right) \geq 1+\nu_2\left(17^{2^{n}}-1\right).\tag{2}$$