# Question regarding Hensel's Lemma

Hensel's Lemma

Suppose that f(x) is a polynomial with integer coefficients k is an integers with $k \geq 2$, and p is 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,

-

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.
Thanks, I saw what I missed now. I really didn't know that we have all other solutions: $3, 8, 13, 18, 23$. By the way, how can I use "hence" correctly? – Chan Mar 13 '11 at 9:31
@Chan: Grammatically, your use of the word "hence" was fine. I was just trying to indicate where the logic went wrong. Your solution was correct up to the sentence "Hence $x\equiv 3\pmod{25}$." But that sentence is wrong since $x$ could be 3, 8, 13, 18, or 23 modulo 25. – Anton Geraschenko Mar 13 '11 at 18:05