Number of Solutions Mod $2^k$ I am trying to solve this problem and would appreciate any direction: Let $a\in \mathbb Z$ with $a ≡ 1 \pmod 8$ and $k\in \mathbb N$ with $k ≥ 3$ be given. Prove that $x^2 ≡ a \pmod {2^k}$ has precisely $4$ solutions
I have worked out that the solutions always take the form $\pm (2^{k-3}+1)$ and $\pm (2k+1)$ but do not know how to show this is always true and that these are the only solutions.
The previous questions on this assignment have all involved Hensel's Lemma but I am not sure if this can be applied for $p=2$.
 A: Hensel certainly does apply here. Write $a=1+8k$, and then we want to solve $X^2=1+8k$. Set $Y=(X-1)/2$, $X=2Y+1$, and substitute to get $Y^2+Y-2k=0$, to which you now apply Hensel to get a root $Y=y_0$, and a root $x_0=2y_0+1$ that solves the original equation $X^2=a=1+8k$ modulo $2^k$.
You now have one root of $X^2\equiv a\pmod{2^k}$, and you want to find all. But if $\rho$ is another root, then $a/\rho$ is a square root of unity modulo $2^k$, so you need only find all $r\pmod{2^k}$ with $r^2\equiv1\pmod{2^k}$. There are four, and here’s the reason:
The group of odd numbers modulo $2^k$ is of form $C_2\times C_{2^{k-2}}$, where the factors are cyclic groups of the indicated order. More precisely, it’s $\{\pm1\}\times\bigl((1+4\Bbb Z)\big/(1+2^k\Bbb Z)\bigr)$, and the elements of order two here are $\pm(1\pm2^{k-1})$, so that your four square roots of $a$ are $\pm x_0\cdot(1\pm2^{k-1})$, where $x_0$ is the number you found before.
Perhaps the most interesting example can be gotten by looking at $a=-7$; for fun, let’s take $k=8$. Your first square root (via Hensel) is $x_0\equiv181\pmod{256}$. The others are $-181\equiv{75}$, $181\cdot129\equiv53\pmod{256}$, and $-53\equiv203\pmod{256}$
