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.

I need to use the Hensel-Newton method (aka Hensel Lifting) to find all solutions of:

$$x^2 + x + 47 \equiv 0\:(\text{mod } 343)$$

Note: $$ 343 = 7^3 $$

I don't really understand Hensel Lifting so I am not sure where to begin. Can someone help give me a better understanding of Hensel Lifting and how to start this problem?

share|improve this question
    
First we need stuff to lift. The solution $x\equiv 1\pmod{7}$ is obvious. The sum of the solutions is the negative of the coefficient of $x$. Thus the other solution modulo $7$ is $-2$. Now we lift. Actually, we could start modulo $49$, but that would not be in the spirit of the game. –  André Nicolas Feb 18 '13 at 22:40

3 Answers 3

Let's start modulo $7$. By trial and error, we find $x^2+x+5\equiv 0\pmod 7$ has the solutions $x\equiv 1$, $x\equiv 5$. Now if $x^2+x+47\equiv 0\pmod{49}$ then $x=x_0+7y$ with $x_0\in\{1,5\}$. Hence $x^2+x+47=(x_0^2+14x_0y+49y^2)+(x_0+7y)+47\equiv (x_0^2+x_0+5)+7\cdot(2x_0y+y+6)\pmod{49}$, where we already know that the left hand side is a multiple of $7$. Hence we have to solve $$ \frac{x_0^2+x_0+5}7+(2x_0+1)y+6\equiv0\pmod 7.$$ If $x_0=1$, this leads to $3y+7\equiv 0$, i.e. $y\equiv 0$. If $x_0=5$, we obtain $11y+11\equiv 0$, i.e. $y\equiv 6$. Thus the only solutions modulo $49$ are $x\equiv 1\pmod{49}$, $x\equiv 47\equiv -2\pmod{49}$. Now if $x^2+x+47\equiv 0\pmod{343}$, then $x=x_1+49z$ with $x_1\in \{1,-2\}$. Hence $$ x^2+x+47 = x_1^2+2\cdot 7^2x_1z+7^4z^2+x_1+7^2z+47\\\equiv(x_1^2+x_1+47)+7^2(2x_1+1)z\pmod{343}.$$ Again, this is trivially a multiple of $49$ and we are lead to solve $$\frac{x_1^2+x_1+47}{49}+(2x_1+1)z\equiv 0\pmod{7}.$$ With $x_1=1$, this is $3z+1\equiv 0$, i.e. $z=2$ and $x\equiv99\pmod{343}$. With $x_1=-2$, this is $-3z+1\equiv0$, i.e. $z=-2$ and $x=-100\pmod{343}$.

share|improve this answer
    
thanks! the process makes more sense now –  ker12 Feb 19 '13 at 2:14
    
One question should the equation under the line "again this is trivially a multiple of 49" but congruent to 0 mod 49 instead of 0 mod 7? –  ker12 Feb 19 '13 at 2:30
    
@ker12 No. $49 a\equiv 0\pmod{343}\iff a\equiv 0\pmod 7$. At each lifting stoe, we solve $\bmod p$ (which is fortunate as this is guaranteed to work, unlike solving $\bmod {p^2}$) –  Hagen von Eitzen Feb 20 '13 at 16:32

Begin with

$$f(x)=x^2+x+47=x^2+x+5\pmod 7=(x-1)(x+2)\pmod 7$$

and we have two roots modulo $\,7\,:\;\;1\,,\,-2=5\pmod 7\,$

Now, from Hensel's Lemma's proof , we have

$$s=1+a\cdot7\;\;,\;\;a:=-\frac{f(1)}{7}f'(1)^{-1}=$$

$$-\frac{49}{7}\cdot 3^{-1}=-7\cdot 33=-231=14\pmod {49}$$

so $\,s=1+14\cdot 7=99\pmod {49}=1\pmod{49}\,$ is a root of $\,f(x)\pmod{49}\,$

and

$$a=-\frac{49}{49}3^{-1}=-229=114\pmod{343}\Longrightarrow s=1+114\cdot 49=99\pmod{343}$$

is a root of $\,f(x)\pmod{7^3}\,$...

You can repeat the above for the other root, namely $\,5\pmod 7\,$

share|improve this answer

It's easy: $\rm\: mod\ 7\!:\ f(x) = x^2\!+x+47\equiv x^2+x-2 \equiv (x+2)(x-1)\:\Rightarrow\: x\equiv 1,\: -2.$

Case $\rm 1\!:\,\ x\equiv 1\,\ (mod\ 7).\:$ Thus $\rm\:x = 1\!+\!y,\,\ 7\mid y.\:$ $\rm\: f(1\!+\!y) = y^2\color{#C00}{+3}y+49\ $ hence

$\rm\ mod\ 49\!:\ 7\,|\,y\:\Rightarrow\: y^2\!\equiv 0\:$ $\Rightarrow$ $\rm\: f(1\!+\!y) \equiv 3y\equiv 0\: \Rightarrow\: y\equiv 0,\,\ $ so $\rm\,\ y = 49z\ $ above gives

$\rm\ mod\ 343\!:\ f(1\!+\!y) \equiv 49^2 z^2 + 3(49z) + 49\equiv 49(3z\!+\!1)\equiv 0\,$ so $\rm\,7\,|\,{3}z\!+\!1\,\Rightarrow\,z\equiv \frac{-1}3\equiv \frac{6}3\equiv 2\ mod\ 7$

$ $ Therefore $\rm\: x \equiv 1\!+\!y\equiv 1\!+\!49z \equiv 1+49\cdot 2 \equiv 99\:\ (mod\ 343).$

Case $\rm\: 2\!:\, x\equiv -2\,\ (mod\ 7).\:$ Similar, but $\rm\:f(y\!-\!2) = y^2\!\color{#C00}{-3}y+49\:$ so $\rm\:z\equiv \frac{-1}{-3}\equiv -2\equiv 5,$ $\rm\,x\equiv 1\!+\!49\cdot 5$

share|improve this answer

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.