# Hensel's lemma and roots of a polynomial mod n

Use Hensel's lemma to find all roots of the polynomial $f(x) = x^3 + 4x + 79$ in $\mathbb Z/(125)$.

Hint: $2$ is the unique root of $f(x)$ in $\mathbb Z/(5)$.

I missed the last class of number theory which was about Hensel's lemma.. and as a result I don't know how to do this one. woudl love some help.

googling Hensel's lemma hasn't been very helpful, the stuff I'm finding is a bit too verbose for me.

-
ugh, how do i get the link to show as an embedded image? – furashu Dec 9 '13 at 11:57
It would be better if you can understand hensel's lemma first and then try this.. what do you think is not clear in hensel's lemma statement? – Praphulla Koushik Dec 9 '13 at 11:59

The idea of Hensel's lemma is to find a solution mod $p$, lift it to mod $p^2$, then to mod $p^3$, etc.

If you know $f(2)\equiv0$ mod $5$ then the solution $x$ mod $5^2$ must be congruent to $2$ mod $5$, so it must be of the form $x\equiv 2+5a$ for some $a\in\{0,1,2,3,4\}$ (think about the integers mod $5^2$ in base $5$) and you can write $f(2+5a)\equiv0$ mod $5^2$ and solve for $a$. Checking $f(2),f(7),f(12),f(17),f(22)$ in that order we find quickly that $f(7)\equiv0$ mod $5^2$.

Now you seek a solution to $f(x)\equiv0$ mod $5^3$. You know $x$ will $7$ mod $25$ so write $x=7+25a$ and solve $f(7+25a)\equiv0$ mod $5^3$ for $a\in\{0,1,2,3,4\}$. Can you do that?

Note in general it is possible to write down explicit formula to lift solutions, which removes the need to use guess-and-check at each stage. One can use the fact that Taylor expansions hold for polynomials even in strange rings like integers-mod-$n$ (as long as the characteristic does not interfere with the denominators of nonzero terms forming, but this won't occur here).

If $f(x)\equiv0$ mod $p^n$ then write $f(x+ap^n)\equiv0$ mod $p^{n+1}$; we seek to solve for $a\in\{0,\cdots,p-1\}$.

The Taylor expansion yields $f(x)+ap^nf'(x)\equiv0$ mod $p^{n+1}$. The next term in the Taylor expansion had $p^{2n}$ in it and $p^{2n}$ is $0$ mod $p^{n+1}$ for all $n>1$. Write $ap^nf'(x)\equiv-f(x)$ mod $p^{n+1}$ and divide by $p^n$ to obtain $af'(x)\equiv-\frac{f(x)}{p^n}$ mod $p$. This is valid because $a\mid b\Leftrightarrow ac\mid bc$ (here with the value $c=p^n$) and $p^n\mid f(x)$ by hypothesis. Therefore $a\equiv -\frac{f(x)}{p^nf'(x)}$ mod $p$ and so the solution to $f(\cdot)=0$ mod $p^{n+1}$ is $x+ap^n=x-f(x)/f'(x)$. Issues occur if $p\mid f'(x)$ in initial stages.

-
this is wonderful, thank you. – furashu Dec 9 '13 at 18:43
using this, i got one unique root for f mod 125: 57. – furashu Dec 9 '13 at 19:21
Please fix a minor mistake: it must be $f(12)$ instead of $f(13)$. It isn't significant, but might confuse beginners if left uncorrected. – Alex M. Jan 4 '15 at 21:31