Find all solutions of the congruence $x^3 - 3x + 2 \equiv 0 \pmod {25}$

Question

I know that the above problem is equivalent to:

$x^3 - 3x + 2 \equiv 0 \pmod {5^2}$

So: Let $f(x) = x^3 - 3x + 2$ and $f'(x) = 3x^2 - 3$

1. Solve for: $f(x) = x^3 - 3x + 2 \equiv 0 \pmod {5}$

-> $x_1 = 1 + 5k_1$ (found 1 as a soln mod 5)

Lift $x_1 \equiv 1 \pmod {5}$ $\iff$ $x_1 = 1 + 5k_1$

$\iff$ By Binomial $f(x_2) = f(1 + 5k_1)$ $= f(1) + f'(1)5k_1$ $(mod5^2)$

I do not know how to proceed from here because I get $0mod5^2$ after evaluating the above.

Please advise. Also let me know if there is a polynomial congruence calculator of which I can use to check my work for similar questions. This is the only one I found: https://www.alpertron.com.ar/QUADMOD.HTM

Thanks.

Answer 1

I would simply factor the polynomial as $(x-1)^2(x+2)$. The $(x-1)^2$ factor is zero whenever $x\equiv 1\bmod 5$, and $x+2\equiv 0$ gives an additional solution $\bmod 25$. Since not both factors can be multiples of $5$, this exhausts the possibilities giving the solution set $\{1,6,11,16,21,23\}$.

Comparing this result with your method we see what happened when $x\equiv 1\bmod 5$. Because all corresponding residues and not just one residue $\bmod 25$ are admitted with that $(x-1)^2$ factor, the Hensel lifting method does not discriminate when you go up to $\bmod 25$. You lift $x\equiv 1\bmod 5$ to all $5k+1$ residues $\bmod 25$. To get any discrimination you have to go at least to the next power of $5$, $\bmod 125$, which you do not do here.