# Taking square roots modulo $2^N$

I was trying to solve $y^2 - y \equiv 16 \pmod{512}$ by completing the square. Here is my solution.

\begin{align} y^2 - y &\equiv 16 \pmod{512} \\ 4y^2 - 4y + 1 &\equiv 65 \pmod{512} \\ (2y-1)^2 &\equiv 65 \pmod{512} \\ 2y - 1 &\equiv \pm 33 \pmod{512} &\text{Found by pointwise search.}\\ 2y &\equiv 34, -32 \pmod{512} \\ y &\equiv 17, -16 \pmod{256} \\ y &\in \{17, 273, 240, 496\} \pmod{512} &\text{These values need to be verified.}\\ y &\in \{240, 273\}\pmod{512} \end{align}

I had to solve $x^2 \equiv 65 \pmod{2^9}$ by a pointwise search. Is there any systematic method for solving equivalences of the form $x^2 \equiv a \pmod{2^N}$, or more generally $x^2 \equiv a \pmod{p^N}$ for a prime number $p$.

• This seems to be related numbertheory.org/php/squareroot.html Commented Aug 16, 2018 at 23:09
• The original equation is actually easier to solve if you use a computation based on the proof of Hensel's lemma. (That's because $y^2 - y$ has a nonzero derivative $\pmod{2}$ but $z^2$ doesn't.) Commented Aug 17, 2018 at 0:12

Can you solve it in $$p$$-adics?

For any $$2$$-adic integer $$n$$ we have the familiar Taylor/binomial-power series for $$\sqrt{1+8n}$$:

$$\sqrt{1+8n}=1+(1/2)(8n)-...$$

All omitted terms vanish $$\bmod 512$$ when $$n$$ is a multiple of $$8$$, thus with $$n=8$$

$$\sqrt{65}\equiv 1+(1/2)(8×8) \bmod 512$$

$$\sqrt{65}\equiv 1+32\equiv 33 \bmod 512$$

So one square root (the root closer to $$1$$ in $$2$$-adics) is $$33 \bmod 512$$.

For reference here are more terms in the binomial expansion used above:

$$\sqrt{1+8n}=1+(2^2)n-(2^3)n^2+(2^5)n^3-(5×2^5)n^4+(7×2^7)n^5-(21×2^8)n^6+(33×2^{10})n^7-(429×2^9)n^8+...$$

This is sufficiently many terms to obtain at least eleven bits in the square root ($$\bmod 2048$$) for any integer $$n$$ (not just multiples of $$8$$ as above); the exponent on $$2$$ is at least $$11$$ in all subsequent terms. The exponent on $$2$$ is always at least the number of terms rendered (e.g. $$2^9$$ in the ninth term), thus guaranteeing convergence in $$2$$-adics. Note also that for a conventional integer square the obtained square root is one greater than a multiple of $$4$$, which in conventional algebra could be the negative root (e.g. $$\sqrt{9}=-3$$).

• This is a great answer. I love p-adic number theory but I am very rusty at it. It seems that I should reintroduce myself to it. Commented Aug 17, 2018 at 0:53

A basic refinement would be to use the fact that if $x^2\equiv y \pmod{p^N}$, then for every $N'<N$ we also have $x^2\equiv y\pmod{p^{N'}}$. You might as well assume $y$ is coprime to $p$, since otherwise you can easily pull out its factors of $p$.

You can then proceed as follows: Find every solution $x$ to this mod $p$. Then, each of these solutions could lift to $p$ things mod $p^2$ - so you can find the solutions mod $p^2$ checking those. Then you can lift again to $p^3$ and so on - and, since there will be at most four* square roots mod $p^N$ (and only two if $p$ is odd). Thus, you'll only have to check about $4pN$ values for this method to work - a lot better than checking $p^N$ values - but wait, we can do even better!

Note that the actual lifting step can be further simplified: If we know that $x^2\equiv y\pmod{p^N}$, then we can try looking for some $z=x+p^Nc$ such that $z^2\equiv y\pmod{p^{N+1}}$. Working this out gives $x^2+2p^Nc\equiv y\pmod{p^{N+1}}$, which is easy to solve for $c$ (or, if $p=2$, we find that $c$ doesn't even matter - half of our previous square roots lift to two new square roots, and the other half don't lift at all!). Doing this, once you figure out the square root mod $p$, it's basically clean sailing from there.

As for actually solving $x^2\equiv y\pmod{p}$, there are some ways - for instance, if $p=4k+3$, you can find one using Fermat's little theorem, but it seems you're interesting in small primes (e.g. $2$) where it's not hard to check every possible $x$.

(*I also should explicitly point out that, for $k\geq 3$, there are four solutions to $x^2=1\pmod{2^k}$ - and consequently, any number with a square root actually has four square roots - the ones you missed for $65$ mod $512$ were $\pm 223$, which can be found by adding $256$ to your existing roots, since adding $256$ doesn't change the square mod $512$.)

• Thanks for pointing out the error. Just by dumb luck, my solution reinserted the $\pm 223$ when I reduced the congruence to $\mod{256}$. Commented Aug 17, 2018 at 0:50

This isn't a general method, but here's a neat trick if $$2^k|a-1$$ for some large enough $$k$$.

Claim. If $$x^2\equiv a\bmod 2^n$$ and $$a\equiv 1\bmod 2^k$$, with $$n\leq 2k$$, then

$$x\equiv \pm \frac{a+1}{2}\bmod 2^{n-1}.$$

Proof. As there are only two residue classes $$\bmod 2^{n-1}$$ that will satisfy this, it suffices to show that these both do. Setting $$b=(a+1)/2$$ we need to show that

$$b^2\equiv a=2b-1\bmod 2^n.$$

Indeed, this is equivalent to

$$2^n|(b-1)^2 \Leftrightarrow b\equiv 1\bmod 2^{\left\lceil\frac{n}{2}\right\rceil},$$

which is itself equivalent to

$$a\equiv 1\bmod 2^{\left\lceil\frac{n}{2}\right\rceil},$$

which is true as $$\left\lceil\frac{n}{2}\right\rceil \leq k$$.

So, since we have $$x^2\equiv a\bmod 2^9$$ and $$a\equiv 1\bmod 2^6$$, we have that $$x\equiv \pm \frac{a+1}{2} = \pm 33\bmod 2^8.$$

A similar result holds in general:

If $$p$$ is an odd prime with $$x^2\equiv a\bmod p^n$$ and $$a\equiv 1\bmod 2^k$$ with $$n\leq 2k$$, then

$$x\equiv \pm \frac{a+1}{2}\bmod p^n.$$

This can be proven in nearly identical fashion.