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.

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.

share|improve this question
    
ugh, how do i get the link to show as an embedded image? –  furashu Dec 9 '13 at 11:57
3  
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

1 Answer 1

up vote 3 down vote accepted

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(13),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.

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

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.