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

When $n\ge 3$, the number of solutions of $x^2\equiv 1\pmod{2^n}$ is $4$. The solutions are $x=\pm 1\pmod{2^n}$ and $x\equiv \pm 1+2^{n-1}\pmod{2^n}$.
Proof: We want $x^2-1\equiv 0\pmod{2^n}$, that is, $(x-1)(x+1)\equiv 0\pmod{2^n}$. Since $x$ must be odd, the gcd of $x-1$ and $x+1$ is $2$. Either all of the $2$'s come from $x-1$, or all the $2$'s come from $x+1$, or $n-1$ of them come from one of $x-1$ or $x+1$, and $1$ of them comes from the other.
To connect this with square roots, note that $u$ and $v$ are square roots of $a$, then $uv^{-1}$ is a square root of $1$, and conversely. So if $a$ has a square root, it has $4$ of them.
To show all $a$ congruent to $1$ mod $8$ have a square root, we use a counting argument. Note that there are $2^{n-3}$ numbers between $1$ and $2^n-1$ that are congruent to $1$ modulo $8$, and $2^{n-1}$ odd numbers. Since the squaring function is $4$ to $1$, it must be the case that every number congruent to $1$ modulo $8$ is the square of something.
