Square roots modulo powers of $2$ Experimentally, it seems like every $a\equiv1 \pmod 8$ has $4$ square roots mod $2^n$ for all $n \ge 3$ (i.e. solutions to $x^2\equiv a \pmod {2^n}$)
Is this true?  If so, how can I prove it? If not, is it at least true that the maximum (over $a$) number of square roots of $a$ mod $2^n$ is bounded by some polynomial in $n$?

If $n\ge3$ and $a=8k+1$ then $a$ has exactly four distinct square roots modulo $2^n$.
Proof that there is at least one square root: use induction.  The case $n=3$ is easy to check; if $x^2\equiv a\pmod{2^n}$ then $x^2=a+2^nk$ for some integer $k$; it is easy to see that $x$ is odd and so
$$(x+2^{n-1}k)^2=a+2^nk(1+x)+2^{n+1}(k^22^{n-3})\equiv a\pmod{2^{n+1}}\ .$$
Finding all square roots: since $a\equiv x^2\pmod{2^n}$ we need to solve $y^2=x^2\pmod{2^n}$.  This gives
$$2^n\mid (y-x)(y+x)\ .$$
Each factor on the RHS is even; but not both are divisible by $4$ as then their sum $2y$ would be a multiple of $4$, which is impossible as $y$ is odd.  So we have
$$2^{n-1}\mid y-x\quad\hbox{or}\quad 2^{n-1}\mid y+x\ .$$
This gives the four possibilities
$$y\equiv x\,,\ y\equiv x+2^{n-1}\,,\ y\equiv -x\,,\ 
  y\equiv -x+2^{n-1}\pmod{2^n}\ ;$$
it is not hard to check that they are all different modulo $2^n$, and that they are in fact square roots of $a$.
