Find all congruence solutions using Hensel's Lemma

Question

I have to find all the solutions to the congruence $x^2 = -6(\text{mod}\, 625)$ using Hensel's lemma and I find it quite difficult. If anyone could point me to the solution I'll be grateful, thanks in advance.

Answer 1

My first post here, so please excuse me if I'm not doing this right.

In response to Stefan4024's post above, $5^4 = 625$. You erroneously wrote $5^3 = 625.$

To solve the problem, you only need to lift twice.

After finding $x = \pm 2 ~(\text{mod } 5)$ or $x = 2, 3$ to be the solutions of $f(x) = 0 ~(\text{mod }5)$, the solutions can be lifted $(\text{mod }5^2)$ or $(\text{mod }25).$

After that, just a single lift to (mod $5^4$) or (mod $625$) is required. This is because one can lift a solution (mod $p^k$) to (mod $p^{m+k}$) as long as m is less than or equal to $k$. In the first lift (from $5$ to $25$), $m = k = 1$, and in the second lift (from $25$ to $625$), $m = k = 2$.

Doing this for both solutions $x = 2$ and $x = 3 ~(\text{mod }5)$ gives the respective solution sets for $f(x) = 0 ~(\text{mod }625)$ as :

$$x = 162 + 625n$$

and

$$x = 463 + 625n$$

where $n$ can take any integer value.

The solutions can be expressed more compactly as:

$$x = 162 \text{ or } 463 ~~(\text{mod }625)$$

Answer 2

The idea behind Hensel lifting ($p\ne2$):

$$x^2\equiv a~(p^n)\implies \exists\bar{x}:\begin{cases}\bar{x}\equiv x~(p^n) \\ \bar{x}^2\equiv a~(p^{n+1})\end{cases}$$

Setting $\bar{x}=x+bp^n$:

$$(x+bp^n)^2\equiv a~(p^{n+1})\iff x^2+2bxp^n\equiv a~(p^{n+1})\iff b\equiv\frac{a-x^2}{2xp^n}~(p).$$

Note the division makes sense since $p^n\mid(a-x^2)$ by hypothesis. Thus at each stage

$$\bar{x}\equiv x+\frac{a-x^2}{2x}.$$

In particular ($a=-6$ and $p=5$),

$\quad$ mod $5$: $~~\quad x^2\equiv-6\Leftrightarrow x^2\equiv4\Leftrightarrow x\equiv\pm2\equiv2,3$

$\quad$ mod $5^2$: $\quad \displaystyle x\equiv2+\frac{-6-4}{4},3+\frac{-6-9}{6}\equiv \,?,?$

You will need to find inverses of units mod $p^n$ (e.g. of $4,6$ mod $5^2$) in general. Can you simplify the above two expressions mod $5^2$? Can you continue on further to $5^3$ and $5^4$?

Answer 3

I'l just solve this example, because DonAntonio and anon explained the theory.

We need to find all solutions for $x^2 \equiv -6 (\mod 625)$, in other words, the function is $f(x) = x^2 + 6$ and we need to find solutions that'll satisfy this condition:

$$ f(x) \equiv 0 \pmod{p^3} \text{, where p = 5, because 625 = $5^3$}$$

Using Hensel lemma first we find solution that satisfy this condition:

$$ f(x) \equiv 0 \pmod 5$$

By guessing we obtain that:

$$ f(2) = 2^2 + 6 \equiv 0 \pmod 5 \text{, so $x_1$ is 2}$$

From Hensel's Lemma we know $x_2 = x_1 + pt$,

$$f(x_2) = f(x_1 + pt) \equiv f(x_1) + ptf'(x_1) \pmod{p^2}$$

So in order $f(x_2) \equiv 0 \pmod{p^2}$ then also this need to be true so we have:

$$f(x_1) + ptf'(x_1) \equiv 0 \pmod{p^2}$$

We know that $p$ divides every number so we divide everything by $p$:

$$\frac{f(x_1)}{p} + tf'(x_1) \equiv 0 \pmod p$$

$$\frac{10}{5} + 4t \equiv 0 \pmod 5$$ $$ 2 + 4t \equiv 0 \pmod 5$$ $$ 1 + 2t \equiv 0 \pmod 5$$ $$ 2t \equiv -1 \equiv 4 \pmod 5$$ $$ t \equiv 2 \pmod 5$$

We obtain that $t = 2$ and for $x_2 = 2 + 2 \cdot 5 = 12$

And indeed $f(12) \equiv 0 \pmod{5^2}$

Now we continue: $x_3 = x_2 + tp^2$

$$f(x_3) = f(x_2 + tp^2) \equiv f(x_2) + tp^2f'(x_2) \pmod{p^3}$$

$$f(x_2) + tp^2f'(x_2) \equiv 0 \pmod{p^3}$$ $$\frac{f(x_2)}{p^2} + tf'(x_2) \equiv 0 \pmod p$$ $$\frac{150}{25} + 24t \equiv 0 \pmod 5$$ $$ 6 + 24t \equiv 0 \pmod 5$$ $$ 1 + 4t \equiv 0 \pmod 5$$ $$ 4t \equiv - 1 \equiv 4 \pmod 5$$ $$ t \equiv 1 \pmod 5$$

The smallest integer solution is $x_3 = 12 + 25 = 37$.

So to find all solution you need to find all solution to the initial function then try with every $t$ that satisfy upper equations. You can't find all solution, because there is infinite amount of them.

Remember there are infinitely many solutions to the initial equation, cause every $x_1 \equiv 2,3 \pmod 5$ satisfy it.

Answer 4

Another approach of the same way Anon already wrote about but, imo, slightly easier to follow recursively. Put

$$f(x):=x^2+6\;,\;\;\text{and let us begin with}$$

$$f(x)=0\pmod 5\iff x^2=-6=4\pmod 5\iff x=\pm 2\pmod 5$$

We check that $\,f'(\pm2)=\pm 4\neq 0\pmod5\;$ , and we define (let us fix $\,r=2\;$ for simplicity)

$$t:=-\frac{f(2)}{5}f'(2)^{-1}\;,\;\;\text{with}\;\;-\frac{f(2)}5\in\Bbb Z\;,\;\;f'(2)^{-1}\in\Bbb F_5\;$$

so that the whole multiplication is done n the finite field, and thus

$$t:=-\frac{10}5\cdot4=-8=2\pmod 5\;,\;\;\text{and then we define:}$$

$$s:=2+(2)\cdot5=12\pmod{5^2}$$

You can now check that indeed $\,f(12)=0\pmod{5^2}\;$ and we can repite the process:

$$t:=-\frac{f(12)}{5^2}\cdot f'(12)^{-1}=-6\cdot(-1)=6=1\pmod5\implies$$

$$s:=12+1\cdot 25=37\pmod{5^3}$$

Once again, it's easy to check that $\;f(37)=0\pmod{5^3}\;$ ...and etc.

The advantage in the above is that in every step it is just a matter of substitution and in the fraction for $\,t\,$ you always get, of course, an integer.

The reason for this is that we assume we have a root $\,f(r)=0\pmod{p^k}\;$ and now we want a root for $\;f(x)=0\pmod{p^{k+m}}\;$ . If you carry on these evaluations from the beginning (i.e., $\,k=1\;$ and in steps of one, then at each step you have to work your way working simply with $\,m=1\implies \pmod{p^m=p}\;$ ...!