Let $n \ge 3$. For $[a] \in (\Bbb Z /{2^n} \Bbb Z)^\times$ the relation $x^2 \equiv a \pmod {2^n}$ has either $0$ or $4$ residue solutions.

Question

Supply a proof for the title question.

My work

I became interested in this after seeing lab bhattacharjee's answer to

$\quad$Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

I've convinced myself that I can prove this using induction and elementary group theory, but it would be interesting to see any rigorous arguments.

If nobody supplies a proof, I will give one in a week or so.

Answer 1

Using the fact that every nonempty subset of natural numbers has a least element, I can prove (minimal criminal technique) that

$\tag 1 x^2 \equiv 1 \pmod{2^n}$

has exactly $4$ solutions.

An alternate method is to attempt to 'position' a fifth solution to the known solutions;
see Bill Dubuque's proof.

Suppose that a solution $[b] \in (\Bbb Z /{2^n} \Bbb Z)^\times$ exists for

$\tag 2 x^2 \equiv a \pmod{2^n}$

Let $Q = \{1, 2^{n-1}-1, 2^{n-1}+1, 2^{n}-1\}$ be the $4$ solutions to $\text{(1)}$. Using elementary group theory we can show that the integers

$\quad b, (2^{n-1}-1)b, (2^{n-1}+1)b, (2^{n}-1)b$

represent $4$ distinct solutions to $\text{(2)}$.

If $c$ is any solution to $\text{(2)}$ then

$\quad \large c b^{-1} \in Q$

and so $\large (c b^{-1})b$ has already been accounted for.

This completes the proof.