How to solve $x^{2}\equiv-7\:\left(128\right)$?

Question

How to solve $x^{2}\equiv-7\:\left(128\right)$ ?

I know that $x^{2}\equiv a\:\left(2^{l}\right)$ is solvable iff $a\equiv1\:\left(8\right)$ which is the case here, but how can we find the solution?

Answer 1

Hint:

As $2^7$ divides $(x+11)(x-11)$ which must be even

As $x+11\pm(x-11)$ are even, both have the same parity and hence both are even

$\implies2^5$ must divide $\dfrac{x+11}2\cdot\dfrac{x-11}2$

Now $\dfrac{x+11}2-\dfrac{x-11}2=11$ which is odd

Hence $\dfrac{x+11}2,\dfrac{x-11}2$ will have opposite parity i.e., exactly one of them must be even and the other must be odd

Answer 2

Having found the solution $x=\pm 11$ you can factorise $x^2+7=(x+11)(x-11)$.

The difference between the factors is $22$ which has just one factor $2$. Both factors have the same parity, and must therefore be even, and you need one of them to be divisible by $64$.

Answer 3

From what @伽罗瓦 and @orion said, we can conclude that: $$128|(x^2-11^2)=(x-11)(x+11) \overset{i+j=7}{\Longrightarrow} \left\{\begin{array}{c}2^i|(x-11) \Longrightarrow x=2^iq_i+11 \\ 2^j|(x+11) \Longrightarrow x=2^jq_j-11 \\ \end{array}\right\} \Longrightarrow 2^jq_j-2^iq_i = 22$$ $$\Longrightarrow 2^{\min(i,j)}|22 \Longrightarrow min(i,j) \in \{0,1\} \Longrightarrow (i,j) \in \{(0,7),(7,0),(1,6),(6,1)\}$$ $$\Longrightarrow\left\{\begin{array}{c} (0,7) \Longrightarrow x=128q-11 \\ (7,0) \Longrightarrow x=128q+11 \\ (1,6) \Longrightarrow x=64q-11 \\ (6,1) \Longrightarrow x=64q+11 \\ \end{array}\right\}\Longrightarrow x=64q\pm11$$

Answer 4

The general method would be to first solve mod 2 and discover that $x \equiv 1 \pmod{2}$. Then "lift" to mod $2^2$, which means that you observe that if $x \equiv 1 \pmod{2}$, then $x\equiv 1$ or $3 \pmod{4}$. Both of these are solutions. So lift them again to mod $2^3$ and get that $x \equiv 1, 3, 5,$ or $7 \pmod{8}$. All of these are solutions. So lift again to mod $2^4$.

Now you get that $x \equiv 1,3, 5, 7, 9, 11, 13,$ or $15\pmod{16}$ but only 4 of these solve the congruence mod 16: 3, 5, 11, and 13.

lift these to mod 32: $3 \pmod{15}$ lifts to $3$ and $19 \pmod{32}$. 5 lifts to 5 and 21. 11 lifts to 11 and 27. 13 lifts to 13 and 29. Of these 8, only 5, 11, 21 and 27 solve the congruence mod 32.

Lift two more times to get all four solutions mod 128.

Answer 5

Hensel lifting is, indeed, the recommended procedure. But you will notice that because the derivative of $x^2+7$ is even at all integer points, it will not work cleanly. So I would also use the following trick in addition.

Consider the polynomial $$f(x)=x^2+x+2.$$ The quadratic formula tells us that its zeros are $(-1\pm \sqrt{-7})/2$ so finding its zeros modulo $128$ will help us. Because $f'(x)=2x+1$ is odd at all integer points, Hensel lifting will work like charm:

If $x_k\in\Bbb{Z}$ and $f(x_k)\equiv0\pmod{2^k}$, then either $f(x_k)\equiv0\pmod{2^{k+1}}$ or $f(x_k+2^k)\equiv0\pmod{2^{k+1}}$ (but not both). In both cases we can "lift" $x_{k+1}=x_k+\epsilon 2^k$ as a solution modulo $2^{k+1}$ with the appropriate choice of $\epsilon\in\{0,1\}$ (exactly one choice will work).

Let's roll.

• We see that $x_2=1$ satisfies $f(x_2)=4\equiv0\pmod{2^2}$, but also that $x_2$ is not a solution modulo $8$.
• The above observation tells us that $x_3=x_2+4=5$ will be a solution modulo $8$. In fact $f(5)=32$ is a solution modulo $32$, so $x_5=5$. But, this is not a solution modulo $64$.
• Therefore $x_6=x_5+2^5=37$ will be a solution modulo $2^6$. In fact $f(37)=1408=11\cdot128$, so we can conclude that $x_7=37$.

By Vieta relations the sum of zeros of $f(x)$ (with derivative invertible modulo $2^\ell$) is $-1$. Therefore the other solution is $-38\equiv90$.

Then we need to revert the initial trick. This doubles the number of solutions.

• If $(-1+\sqrt{-7})/2\equiv 37\pmod{128}$ then $-1+\sqrt{-7}\equiv2\cdot37\equiv10\pmod{64}$ implying $x\equiv11\pmod{64}$ as solutions to $x^2\equiv-7\pmod{128}$.
• If $(-1+\sqrt{-7})/2\equiv -38\pmod{128}$ then $-1+\sqrt{-7}\equiv-76\equiv-12\pmod{64}$. This similarly leads to solutions $x\equiv-11\pmod{64}$.

Warning: Lifting modulo powers of $2$ is special, because there is only a single non-zero residue class for the non-vanishing derivative, and hence only a single possible way to "improve" a solution modulo a lower power. Leaving the proof of the earlier highlighted inductive step as an exercise for the doubters. It works for lifting the zeros of any polynomial $f(x)$ such that $f'(n)$ is odd for all integers $n$.