# Solve Polynomial Congruence mod $89^2$

Solve $3x^2+6x+5\equiv 0\pmod{89^2}$.

To do this, I first solved $3x^2+6x+5\equiv 0\pmod{89}$.

This has a solution since $3x^2+6x+5 = 3(x+1)^2 + 2$ and $3(x+1)^2 \equiv -2 \pmod{89}$ has a solution since $(3,89)=1$, we can check whether $(x+1)^2 = 3^{-1}(-2)\pmod{89}$ which is equivalent to calculating $\left(\dfrac{3^{-1}(-2)}{89}\right)$. The value is 1, so this is a quadratic residue. Since we have a number that when squared gives us this, we have a solution to the polynomial congruence mod 89. Since we have 1, we have 2 since solutions come in pairs $\{\pm x_0\}\pmod{89}$.

Here is my question: without finding the residue, how can I use Hensel's lemma to see whether I can lift the solutions to solutions modulo $89^2$?

I hope someone can help. Thank you.

-
The only requirement to be able to lift it is to make sure that $f'(r)\not\equiv 0\pmod{89}$. The derivative is $6x+6 = 6(x+1)$; in order to verify that it is not $0$ modulo $89$, all you have to do is make sure that the answer you got $\pm x_0$, is not $1$, which seems easy. –  Arturo Magidin Dec 12 '11 at 0:46
EDIT: Okay, so if I get $x_0\neq \pm 1$, then $89\nmid 6(x_0+1)$. This will generate two new solutions modulo $89^2$ then. But if $89\mid 6(x_0+1)$, I have to check whether $89^2\mid 3x_0^2 +6x_0+5$. If it does, I get 89 new solutions for each $x_0$. If not, I have no solutions for either of them. Is that right? –  mathmath8128 Dec 12 '11 at 0:50
The solutions do lift: the answer you get cannot be $1$ or $-1$, because $3+6+5\not\equiv 0\pmod{89}$, and $3-6+5\not\equiv 0\pmod{89}$. By Hensel's Lemma, if $f(r)\equiv 0\pmod{89}$ and $f'(r)\not\equiv 0\pmod{89}$, then $r$ lifts uniquely to a solution $s$ of $f(s)\equiv 0\pmod{89^2}$. So each of $x_0$ and $-x_0$ lift to unique solutions modulo $89^2$ (in fact, you can lift them to solutions modulo $89^k$ for any $k$). –  Arturo Magidin Dec 12 '11 at 0:54
Perfect OK I was just making sure. I will delete the post. I didn't know if it was enough to test $\pm 1 \pmod{89}$. –  mathmath8128 Dec 12 '11 at 0:55
In this case it is, because those are the only possible values of $r$ that can mess up your Hensel lift. In general, you can check the zeros of $f'(x)$ (assuming you can find them, which in this instance we can) and see if any of them satisfy the original equation. Essentially, you are checking to see whether the polynomial has repeated roots modulo $p$. Since this polynomial is not a perfect square modulo $89$, its roots are simple roots and so they lift. –  Arturo Magidin Dec 12 '11 at 0:57