Application of Hensel's lemma $x^2 \equiv a (\mod 2^L)$

Question

Let $a$ be an odd integer. And $L \geq 1$. I would like to know the number of solutions modulo $2^L$ to the congruence $$ x^2 \equiv a \pmod {2^L}. $$ Is it possible to conclude that there is number $C> 0$ such that the number of solutions modulo $2^L$ to the congruence is at most $C$ for any $L$? Thank you.

Answer 1

Let us trace along an argument inspired by the proof that $a \equiv 1 \pmod{8}$ has square roots in $\mathbb{Z}_2$, in order to find out the number of square roots $\pmod{2^L}$.

First, since $a$ is odd and is a square, we know that if $L \ge 3$, then $a \equiv 1 \pmod{8}$; say $a = 8b + 1$. Then for $n^2 \equiv a \pmod{2^L}$, we must have $n$ odd, say $n = 2m + 1$. Then \begin{align*} (2m+1)^2 \equiv 8b+1 \pmod{2^L} & \Leftrightarrow 4m^2 + 4m + 1 \equiv 8b+1 \pmod{2^L} \\ & \Leftrightarrow m^2 + m \equiv 2b \pmod{2^{L-2}}. \end{align*} Now, by Hensel's lemma, since $p(x) = x^2 + x$ is a polynomial with $p(0), p(1) \equiv 0 \equiv 2b \pmod{2}$ and $p'(0), p'(1) \equiv 1 \pmod{2}$, for any given $b$, there are exactly two solutions of $m^2 + m \equiv 2b \pmod{2^{L-2}}$ for $m \pmod{2^{L-2}}$: one with $m$ even, and one with $m$ odd. Now, each of these two solutions determines $n \pmod{2^{L-1}}$; we thus get at most 4 solutions $\pmod{2^L}$.

(And in fact, this reflects the comment by J. W. Tanner that if $n$ is a solution, then the general solutions are $\pm n$ and $2^{L-1} \pm n$. To see this, note that if $m_0$ is one of the roots of $m^2 + m \equiv 2b \pmod{2^{L-2}}$, then $-1 - m_0$ is also a root. This also implies there are exactly 4 solutions in all cases with $L \ge 3$, since $n$ odd and $L \ge 3$ implies all these values are distinct.)

Answer 2

Hint: if $x^2 - 1 = (x+1)(x-1)$ is divisible by $2^L$ with $L \ge 3$, exactly one of $x+1$ and $x-1$ is divisible by $2^{L-1}$.