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

• This is discussed in Example 3.18 (page 58) of elementary number theory by Jones & Jones. Jan 23, 2021 at 12:29

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.

• To be clear, at least $n-1$ $2$'s come from one of the terms, since $(x+1)(x-1)$ could have more than $n$ factors of 2.
– qwr
Sep 22, 2021 at 5:13

The modular equation $x^2\equiv1\pmod{2^n}$ can be written this way: $$(x+1)(x-1)\equiv0\pmod{2^n}$$ It is clear from here that $x+1$ and $x-1$ are even. Since the difference between $x+1$ and $x-1$ is $2$, one of these numbers is a multiple of $2$ but not of $4$. This implies that the other one must be multiple of $2^{n-1}$.

This gives only four possibilities: $x\equiv1$, $x\equiv-1$, $x\equiv2^{n-1}+1$ and $x\equiv2^{n-1}-1$, that are distinct because $n\geq3$ (all these congruences are modulo $2^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$.