2
$\begingroup$

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,

1 Answers 1

1

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.

  • 0
    @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.2011-03-13