Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.