Hensel Lifting and solving with mods

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?

-
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

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\,$

-

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}$.

-
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

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$

-