# Newton-Hensel method in number theory

I am trying to find roots of the polynomial $f(x)=x^3 +1 mod (11^2)$ using the Newton-Hensel method.

By inspection, in mod 11, I see the only possible solution is -1. Plugging integers of this form into newton's formula I get: $(f(11k-1)/f'(11k-1) - 1$ for the new class of roots mod $11^2$ which finally simplifies to -1/(22k+1). Unless I made a dumb error, I don't see how I am any better off with this expression, I now have 121 integers to check if I want to solve for the roots of this function in this raised modular class explicitly.

Also, Any resources on this method would be appreciated, I haven't found much online.

• Because 22 is divisible by 11, you have 22(k+11) = 22k (mod 121). So you still only have 11 values of k to try. – Ted Nov 2 '15 at 3:06
• sorry how does that follow? I am in mod $11^2$ at that point right? – qbert Nov 2 '15 at 3:18
• The idea of Hensel's lemma is that it allows you to solve - no 'trying'- for the solution mod $p^{k+1}$, if you know it already mod $p^k$. For instance there is no $f'(11k -1)$ needed, only $f'(-1)$. My answer below might help... – peter a g Nov 2 '15 at 3:21
• I am not familiar with this method,but there is another method :If p is an odd prime then multiplication mod $p^n$ (n>0) on the members of 1,..., $p^n-1$ that are not divisible by p, is a cyclic group. – DanielWainfleet Nov 2 '15 at 3:31

As you pointed out, $-1$ is the unique solution to $x^3 +1 \equiv 0\pmod {11}$, but not only by inspection, but - just a remark - also because the ration of any two possible solutions is a third root of unity, and $3 \not|\, 11-1$. At any rate, any solution $\pmod {11^2}$ is of the form $-1+ 11k$, where $k$ is unique $\pmod {11}$.

Using "Taylor series," $$f( -1 + 11 k) \equiv f(-1) + 11 k f'(-1) \pmod {11^2}.$$ Now, if you want the LHS $\equiv 0 \pmod {11^2}$ (i.e., 'doing' Hensel's lemma), one has (evaluating $f(-1)$ and $f'(-1)$) $$0 \equiv 0 + 11k 3 (-1)^2 \pmod {11^2}.$$ So $k \equiv 0\pmod {11}$, and $x=-1+ 11\cdot 0$ is the unique solution to $f(x)\equiv 0 \pmod {11^2}$.

Edit: This is to illustrate/complete (and correct one of) the comments I made below. Suppose, instead of starting with $-1$, as you did, one had (maliciously) started with $10$, which is of course congruent to $-1$ modulo $11$. Then, $f(10)\equiv 0 \pmod {11}$. If one wanted to use Hensel's lemma to find a $k$ such that $f(10 +k 11)\equiv 0 \pmod {11^2}$ one would, as above, use "Taylor:"

$$f( 10 + 11 k) \equiv f(10) + 11 k f'(10) \pmod {11^2}.$$ Since we want the LHS $\equiv 0 \pmod {11^2}$, one gets, after using on the RHS that $f(10)\equiv 33 \pmod {11^2}$ and $f'(10) = 3\cdot 10^2$, that $$0 \equiv 33 + 11\cdot k \cdot 3\cdot 10^2 \pmod {11^2}.\tag{*}$$ Dividing by $11$, one has to solve the equation $$0 \equiv 3 + k\cdot 3\cdot 10^2 \pmod {11}.\tag{**}$$ Substituting $10\equiv -1$ above, one gets $k \equiv -1\pmod {11}$: $x=10+ 11\cdot -1=-1$ is the unique solution to $f(x)\equiv 0 \pmod {11^2}$ - which is the same as before.

Note: Hensel's algorithm needs both that $f(a)\equiv 0 \pmod p$ and $f'(a) \not\equiv 0 \pmod p$ (here with $p=11$, and $a\equiv -1\pmod {11}$):

The fact that $f(a)\equiv 0 \pmod {p}$ allows one to divide by $(*)$ by $p$.

The fact that $f'(a) \not\equiv 0 \pmod p$ allows one to divide by $f'(a) \pmod p$ and solve for the (unique) $k \pmod p$ in $(**)$ to make $(*)$ hold true.

• This is awesome (I had no idea taylor's theorem would come up in number theory, it really is an amazing theorem). Just a couple of questions: 1) Where does the error term go? 2) isn't the solution that k is congruent to zero mod $11^2$? I.e if -1 is a solution iff. k is congruent to 0 mod $11^2$? 3) I guess also, is this system surefire? And in what way is it different from Hensel's Lemma? – qbert Nov 2 '15 at 3:43
• Well - the 'Taylor series' is a bit of whimsy here: all I used above $$f(a + \delta) = f(a) + f'(a)\delta + O(\delta^2).$$ Also, it's a bit problematic to say Taylor series, because there are those factorials in the denominator in higher order terms - but I wanted you to see what was happening explicitly. – peter a g Nov 2 '15 at 3:50
• So why are we able to have the above identity? Also why do the order of delta squared terms disappear? Also, can you explain the last line of your post? – qbert Nov 2 '15 at 3:55
• OK - 1) the 'error term' is in mod $11^2$. 2) in the notation of my previous comment $\delta = 11k$ , and so $k$ is determined mod 11 3) this is Hensel's lemma - you want to solve for $k$ to make the congruence work at the next power of $11$. To see this, if by malice you had chosen, instead of $-1$ as your first guess, $10 = -1+11$, then $f( 10) \equiv 0 \pmod {11}$ but $f(10) \equiv 32 \pmod {11^2}$. Hensel's lemma would have allowed you to 'improve' your initial (malicious) guess. – peter a g Nov 2 '15 at 4:01
• $x^3=-1$ isn't a great example for Hensel's lemma because it has an exact solution -1 in $\mathbb{Z}$ already, so once you start with -1, the later approximations can't get any better. It might be better to try an equation like $x^3 = 2$ instead so you can see the approximations get better at each stage. – Ted Nov 2 '15 at 4:03