Find all congruence solutions using Hensel's Lemma 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.
 A: 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)$$
A: 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$?
A: 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.
A: 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}\;$ ...!
