# Understanding Hensel's Lemma

I am learning Hensel's Lemma and trying to solve the polynomial congruence $$x^5+x^4+1\equiv 0\pmod{81}$$ Now my professor taught us the technique of building up from $p$, to $p^2$, and continuing to $p^k$ by repeated use of the lemma. I think this particular congruence has no solutions.

let $f(x)=x^5+x^4+1$. Then $f'(x)=5x^4+4x^3$. We are using calculating $\pmod{3}$ so we test residues $0,1,2$. $$f(0)=1\not\equiv 0\pmod{3}, f'(0)=0\equiv 0\pmod{3}$$ $$f(1)=3\equiv 0\pmod{3}, f'(1)=9\equiv 0\pmod{3}$$ $$f(2)=49\not\equiv 0\pmod{3}, f'(2)=112\not\equiv 0\pmod{3}$$ So the only residue that works is $r=1$. But since $f(1)\not\equiv 0\pmod{3^2}$, there is no solution.

Is this the correct employment of Hensel's lemma?

$\mathbf{EDIT}$ I'm just looking for verification on whether or not this is correct. I feel pretty confident that it is right, but perhaps someone can just look it over...

-

The fact that $f'(a_0)$ is divisible by $p$ does not in itself forbid the possibility of lifting a modular solution to a higher power of $p$. See the remark by KCd here for a more relaxed condition. You see that his condition does not hold in the present case either.

What you have done shows that a solution cannot be produced by Hensel lifting. Whether this is sufficient to settle the matter depends on the exact form of Hensel lift done in your class. Not knowing that I am a little bit concerned about the possibility that the version of Hensel lifting was only about proving existence of a solution modulo $p^{k+1}$ given a solution modulo $p^k$ and the condition with the derivative. More typically (that's how I would teach it myself!) the non-existence result is that if there are no solutions modulo $p^k$ then there won't be any solutions modulo $p^{k+1}$ either. In other words, Hensel won't give non-existence of solutions.

If that is the case with the version of Hensel lifting in your class, too, then you need to do more. Here you can simply check that your polynomial has no zeros modulo $9$. Just plug in $x=0,1,\ldots,8$.

It is easy to imagine a version of Hensel lifting that does give the non-existence of solutions modulo $9$ by the process you described. In the present case such a version requires you to observe that $f(1)\not\equiv 0\pmod9$ and that $f'(1)\equiv 0\pmod 3$. I'm just worried that this was not covered in your class.

To drive my point home: Consider the polynomial $g(x)=x^5+7x^4+1$ instead of yours. Here $g(1)\equiv0\pmod3$ is the only solution modulo $3$, and $g'(1)=12\equiv0\pmod3$ as in your case. But this time there exists a solution modulo $9$ as well, because $g(1)\equiv0\pmod 9$. Furthermore, we have $g(7)\equiv0\pmod{81}$, so the solution lifts. Notice the difference to your polynomial $f(x)$.

-
Here is how I was shown. Let $f(r)\equiv 0 \pmod{p^{k-1}}$ with p prime, $k\ge 2, r\in \mathbb{Z}$. CASE 1: If $f'(r)\not\equiv 0 \pmod{p}$, solve $f'(r)y\equiv 1\pmod{p}$ for y. Find smallest nonneg int $t$ s.t $t\equiv -\frac{f(r)y}{p^{k-1}}\pmod{p}$. Then $x=r+tp^{k-1}$ is a solution of $f(x)\equiv 0\pmod{p^k}$. CASE 2: If $f'(r)\equiv 0\pmod{p}$ and if $f(r)\equiv 0\pmod{p^k},$ then $x=r+tp^{k-1}$ is a solution of $f(x)\equiv 0\pmod{p^k}$ for $t=0,1,...,p-1$. CASE 3: If case 2 holds except $f(r)\not\equiv 0\pmod{p^k}$, then no solutions –  Lalaloopsy Jul 10 '14 at 17:07
It seems to me that the cases are analogous to systems of equations; case 1 denotes a unique solution (brought about by finding $y=f'(r)^{-1}$. case 2 denotes multiple solutions since there are possibilities due to values of $t=0,1,...,p-1$. And case 3 denotes no solution. I don't know if this analogy holds, but that is how I initialy interpreted it. –  Lalaloopsy Jul 10 '14 at 17:13
Ok. That is a more thorough version of Hensel than I expected. My worries are thus lifted. Notice that in your example CASE 3 applies. You did it correctly. –  Jyrki Lahtonen Jul 10 '14 at 17:22
thank you for your help... –  Lalaloopsy Jul 11 '14 at 1:26