Hensel lifting when not a power of a prime

315 Views Asked by At

Say you have the equation $x^2 + x + 47 = 0$ and that you want to determine the solutions in $\mathbb{Z}/1715 \mathbb{Z}$. Note that $1715 = 7^3 \cdot 5$. Then, using Hensel's lemma, one can find the solutions mod $343$. That's the good news. The bad is that I now have a problem with calculating the inverse. Here's a quick summary of my previous calculations:

$f(1) = 0$ in mod $7$, and Hensel gives $x_1 = 99 \mod 343$, which is a root of $f(x)$ in $\mathbb{Z}/ 343 \mathbb{Z}$. But if I now work in modulo $5$, and if $x_2 = x_1 + 343t$, then the calculation of $t$ leads us to $$t = - \frac{f(x_1)}{343}f'(99)^{-1} = 29 \cdot (199)^{-1}.$$ The problem is that $199$ doesn't have an inverse in $\mathbb{Z}/1715 \mathbb{Z}$. So ... What now? Does it simply mean that there doesn't exist a root in $\mathbb{Z}/1715 \mathbb{Z}$ when starting with $f(1) = 0$ (in mod $7$)?

1

There are 1 best solutions below

2
On BEST ANSWER

What's wrong with solving modulo $343$ and modulo $5$ separately, and then using the Chinese remainder theorem?