Solving congruences with cubics

I want to be able to solve $$x^3 +6x^2+x+5 \equiv 0\mod{13^2} $$

I have used Hensel's Lemma, and currently have: $ f(1+13t_1) \equiv 0\mod{13^2} $ is equivalent to $ 16t_1+117t_1^2+169t_1^3 \equiv -1\mod{13}$ but I don't know where to take it from here?

Solution 1:

If you want to find all solutions to an equation mod $p^2$, you need to start by finding all solutions mod $p$ and then "lift" them to solutions mod $p^2$. For the cubic $x^3+6x^2+x+5$ we have

$$x^3+6x^2+x+5\equiv(x-1)(x-2)(x-4)\mod13$$

so the solutions mod $13$ are $1$, $2$, and $4$.

To "lift" the solution $x\equiv1$ mod $13$, we write $x=1+13u$ and note that

$$x^n=(1+13u)^n\equiv1+13nu\mod13^2$$

(In particular, it's not necessary to compute any of the coefficients of higher-order powers of $u$.) In this way, we get

$$x^3+6x^2+x+5\equiv(1+39u)+6(1+26u)+(1+13u)+5\equiv13+208u=13(1+16u)\mod13^2$$

This is satisfied if $1+16u\equiv0$ mod $13$, which simplifies to $1+3u\equiv0$ mod $13$, from which it's easy to see that $u=4$ does the trick, giving us $x=1+13\cdot4=53$ as one of the solutions mod $13^2$.

I'll leave the lifting of $x\equiv2$ and $4$ mod $13$ as an exercise (unless the OP requests more details), noting only that when writing $x=r+pu$ (for a general root $r$ and prime modulus $p$), we have

$$x^n=(r+pu)^n\equiv r^n+pnr^{n-1}u\mod p^2$$

Remark: I've written $u$ here instead of $t_1$, but one is certainly free to use a notation $x=r+13t_r$. Also, it looks to me like the answer by sirious jumped from a (correct) derivation of $t_1=4$ for the lifting of the root $x=1$ mod $13$ to a (coincidentally correct) conclusion that $x=4$ is a solution mod $13^2$.