# How many solutions does this equation have $x^2 \equiv 1017 (\mod 2^k)$

How many solutions does this equation have $x^2 \equiv 1017 \ \mod 2^k$?

I know that $1017 \equiv 1 \mod 8$?

I think that for $k=1$ we have $x^2 \equiv 1017 \mod 2$ and the solution is $x=1 \mod 2$

and for $k=2$ we have $x^2 \equiv 1017 \mod 4$, so $x^2 \equiv 1 \mod 4$.

(Previously, I wrote that $x^2 \equiv 3 \mod 4$)

What can I do for $k \ge 3$?

I've read somewhere that if $x_k ^2 \equiv a \mod 2^k, \ \ k \ge 3$, this means that $2^k | x^2-a$.

If $\frac{x^2 - a}{2^k}$ is odd, let $i=1$, if it os even, let $i=0$.

Then $x_{k+1}:= x_k + i\cdot 2^{k-1}$ is a solution to $x^2 _{k+1} \equiv a \mod 2^{k+1}$.

Do you think this could be useful?

Could you help me?

Thank you.

• If $1017\equiv 1\pmod 8$ then $1017\equiv 1\pmod 4$. – Thomas Andrews May 24 '13 at 12:03
• Oops, I'll correct that right away. Thanks. – Sandy May 24 '13 at 12:05
• For k=2, if x is an odd number, then x=2k+1 and $x²=4k²+4k+1 \equiv 1 \equiv 1017 \mod 4$ – gvo May 24 '13 at 12:32
• – lab bhattacharjee May 24 '13 at 14:35

Modulo 8 you have four pairwise noncongruent solutions $x=1,3,5,7$. You can "lift" all of those to solutions modulo a higher power of two by a process called Hensel lifting. That process is unique, so you end up with four pairwise noncongruent solutions modulo $2^k$, $k\ge3$.

Another way of seeing is that the solutions must form four residue classes modulo $2^k$ is to observe that the ratio of any two solutions must be a square root of $1$ modulo $2^k$, and it is well known that there are exactly four such residue classes, namely $\pm1$ and $\pm1+2^{k-1}$.

The lifting is very closely related to the process you describe. Assume that you have a solutions $x_k$ modulo $2^k, k\ge3$. In other words, $$x_k^2\equiv1017\pmod{2^k}.$$ Obviously here $x_k$ is then an odd integer. Let's try to find a solution $x_{k+1}=x_k+a2^{k-1}$ that would work modulo $2^{k+1}$. We calculate $$x_{k+1}^2=x_k^2+2^kax_k+2^{2k-2}a_k^2,$$ so $$x_{k+1}^2-1017=(x_k^2-1017)+2^kax_k+2^{2k-2}a_k^2.$$ Here $1017-x_k^2$ is divisible $2^k$, and the last term is divisible by $2^{2k-2}$ and hence by $2^{k+2}$ (here we need the assumption $k\ge3$). So choosing $a=0$ or $a=1$ will make the right hand side divisible by $2^{k+1}$, which is exactly what we wanted.

Once we get this going, we can rinse and repeat as many times as needed.

For example starting with the solution $x_3=1$ modulo $2^3$ ($k=3$). We check that $$x_3^2-1017\equiv1-9\not\equiv0\pmod{16},$$ so we fix the solution by adding a multiple of $2^{k-1}$, so $x_4=x_3+4=5$, which works modulo $16$ as $5^2=25\equiv9\equiv1017\pmod{16}$. As $1017\equiv25\pmod{32}$, it also works modulo $32$, so we choose $x_5=x_4=5$. Modulo $64$ we have $1017\equiv57\not\equiv5^2$, so we "improve" our solution $x_6=x_5+2^{5-1}=5+16=21$ again by adding $2^{k-1}$ to it. As $21^2\equiv57\pmod{128}$, but $1017\equiv121\pmod{128}$, we need to again improve the solution to $x_7=x_6+2^5=53$ to get one that works modulo 128. We continue the sequence as $x_8=x_7=53$, $x_9=x_8+2^7=181$, which is also a solution modulo $2^10=1024$.

The other square roots of $1017$ modulo $1024$ are, as promised, $$-181\equiv843,\qquad (1+512)(181)\equiv693\qquad\text{and}\qquad-693\equiv331.$$

It is hopefully clear that you can keep doing this as long as you wish. We actually get an infinite sequence of square roots of $1017$ modulo an ever increasing sequence of powers of two. As a limit, we get a $2$-adic square root of $1017$, but if you have never heard of $2$-adic numbers, that may not mean anything to you.