Hensel's Lemma
Suppose that f(x) is a polynomial with integer coefficients, $k$ is an integer with $k \geq 2$, and $p$ a prime.
Suppose further that $r$ is a solution of the congruence $f(x) \equiv 0 \pmod{p^{k-1}}$. Then,
If $f'(r) \not\equiv 0 \pmod{p}$, then there is a unique integer t, $0 \leq t < p$, such that
$$f(r + tp^{k-1}) \equiv 0 \pmod{p^k}$$ given by
$$t \equiv \overline{-f'(r)}\frac{f(r)}{p^{k-1}} \pmod{p}$$ where $\overline{-f'(r)}$ is an inverse of f'(r) modulo p.
If $f'(r) \equiv 0 \pmod{p}$ and $f(r) \equiv 0 \pmod{p^k}$, then $f(r+tp^{k-1}) \equiv 0 \pmod{p^k}$ $\forall$ integers t.
If $f'(r) \equiv 0 \pmod{p}$ and $f(r) \not\equiv 0 \pmod{p^k}$, then $f(x) \equiv 0 \pmod{p^k}$ has no solutions with $x \equiv r \pmod{p^{k-1}}$
I'm practicing solving congruence equation using Hensel's Lemma, however, I was a little confused with the last two cases.
To be clear, I use this congruence equation as an example $f(x) = x^4 + 4x^3 + 2x^2 + 2x + 12 \equiv 0 \pmod{625}$
My attempt was:
By inspecting all remainders of $5$, i.e $0, 1, 2, 3, 4$ \
We can see that
$ x \equiv 3 \pmod{5}$ is the solution to $f(x) \equiv 0 \pmod{5}$ \
Apply Hensel's Lemma for $5^2 = 25$, we have:
$$f'(x) = 4x^3 + 12x^2 + 4x + 2$$
And,
$$f'(3) = 4.3^3 + 12.3^2 + 4.3 + 2 = 230 \equiv 0 \pmod{5}$$
$$f(3) = 3^4 + 4.3^3 + 2.3^2 + 2.3 + 12 = 225 \equiv 0 \pmod{5^2}$$
Hence,
$$x \equiv 3 \pmod{5^2}$$
Apply Hensel's Lemma for $5^3 = 125$, we have:
$$f(3) = 225 \not\equiv 0 \pmod{5^3}$$
So $f(x) \equiv 0 \pmod{5^3}$ has no solutions with $x \equiv 3 \pmod{5^2}$. \
Therefore, there are no solutions to $f(x) = x^4 + 4x^3 + 2x^2 + 2x + 12 \equiv 0 \pmod{625}$
What I understood about Hensel's Lemma is, it let us lift up the solution from $p^k$ to $p^{k + 1}$ each time we found a solution of a current $k$. But, in the case 2, when it said for all integers t, I was confused. Does it mean I can use the previous solution with $p^k$. By that I mean, if I have $x \equiv 3 \pmod{5}$, then if case 2 satisfies, then $x \equiv 3 \pmod{25}$?
If the question is vague, please let me know. I will try my best to rewrite it again. Sorry for my poor English writing.
Thanks,
Best Answer
You go off track at the word "Hence". If $f'(3)\equiv 0\pmod 5$ and $f(3)\equiv 0 \pmod{25}$ (I assume you've done this correctly; I didn't check), that means that $x\equiv 3,8,13,18,23 \pmod{25}$ are all solutions modulo 25. You only verified that there are no solutions modulo 125 which are 3 modulo 25. There may still be solutions which are 8, 13, 18, or 23 modulo 25.