0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ted Nov 2 '15 at 3:06
  • $\begingroup$ sorry how does that follow? I am in mod $11^2$ at that point right? $\endgroup$ – qbert Nov 2 '15 at 3:18
  • $\begingroup$ 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... $\endgroup$ – peter a g Nov 2 '15 at 3:21
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Nov 2 '15 at 3:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – qbert Nov 2 '15 at 3:43
  • $\begingroup$ 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. $\endgroup$ – peter a g Nov 2 '15 at 3:50
  • $\begingroup$ 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? $\endgroup$ – qbert Nov 2 '15 at 3:55
  • 1
    $\begingroup$ 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. $\endgroup$ – peter a g Nov 2 '15 at 4:01
  • $\begingroup$ $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. $\endgroup$ – Ted Nov 2 '15 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.