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.

  • 3
    $\begingroup$ If $1017\equiv 1\pmod 8$ then $1017\equiv 1\pmod 4$. $\endgroup$ – Thomas Andrews May 24 '13 at 12:03
  • $\begingroup$ Oops, I'll correct that right away. Thanks. $\endgroup$ – Sandy May 24 '13 at 12:05
  • 1
    $\begingroup$ For k=2, if x is an odd number, then x=2k+1 and $x²=4k²+4k+1 \equiv 1 \equiv 1017 \mod 4$ $\endgroup$ – gvo May 24 '13 at 12:32
  • 1
    $\begingroup$ Related : math.stackexchange.com/questions/25128/… $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.