Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.