How to solve $x^3 + 2x + 2 \equiv 0 \pmod{25}$?

My attempt was: $x^3 + 2x + 2 \equiv 0 \pmod{25}$ By inspection, we see that $x \equiv 1 \pmod{5}$. is a solution of $x^3 + 2x + 2 \equiv 0 \pmod{5}$. Let $x = 1 + 5k$, then we have: $$(1 + 5k)^3 + 2(1 + 5k) + 2 \equiv 0 \pmod{25}$$ $$\Leftrightarrow 125k^3 + 75k^2 + 25k + 5 \equiv 0 \pmod{25}$$ $$\Leftrightarrow 5 \equiv 0 \pmod{25}$$

And I was stuck here :( because k was completely cancelled out, how can we find solution for this equation?

Thanks,

I wanted to post some excerpts from Niven's book that gives a nice recurrence relation to lifting nonsingular roots. I always found it helpful to use as a kind of plug and chug way to go. I also included an example of it in action.

To address your specific problem, you see that $x\equiv 1,3$ are roots mod $5$. However, $$ f'(1)=3(1)^2+2\equiv 0\pmod{5}\quad\text{and}\quad f'(3)=3(3)^2+2\equiv 4\pmod{5} $$ so $x\equiv 3$ is nonsingular, and may be lifted to a solution $a_2$ mod $25$ by Hensel's Lemma. Notice that $\overline{f'(3)}=4$. By the recurrence (2.6) of the excerpt above, you have $$ a_2=3-35(4)\equiv 3+(15)(4)\equiv 3+10\equiv 13\pmod{25} $$ which is the solution found by others. I hope it's useful when the numbers you're working with may not be as nice.

Hint by others, we use Hensel's lemma. By Hensel's lemma we solve $x^{3}+2x+2=0$ (mod 5). This has solution $1$ and $3$. But $1$ satisfies $f'(1)=0$, by Chan's previous work it should be cast aside. Hensel's lemma suggests solutions of the form $3+5k$ with $3(3+5k)^{2}+2\not=0$(mod 5). Hensel's lemma give $k$ to be:

$k(29+90 k+75 k^2)=k^{3}+2k+2$ (mod 5)

Solve this we should get $k=2$. I do not know if this is the best way to solve it.

This shows, that there is no modular zero for $x^3+2x+2\equiv 0 \; (\text{mod}\; 25)$ of the form $x = 1 + 5k$, since clearly $ 5 \not\equiv 0 \; (\text{mod}\; 25)$.

Now go ahead and check $x = 3 + 5k$, because $x \equiv 3 \; (\text{mod}\; 5)$ is the other solution to $x^3+2x+2\equiv 0 \; (\text{mod}\; 5)$.

For this, I think the quickest way is simply to work out the 25 possibilities.

For 0,1,2,...24 you have $x^3+2x+2$ giving 2, 5, 14, 35, 74, 137, 230, 359, 530, 749, 1022, 1355, 1754, 2225, 2774, 3407, 4130, 4949, 5870, 6899, 8042, 9305, 10694, 12215, 13874 equivalent modulo 25 to 2, 5, 14, 10, 24, 12, 5, 9, 5, 24, 22, 5, 4, 0, 24, 7, 5, 24, 20, 24, 17, 5, 19, 15, 24.

So the solution is $x \equiv 13$

Hint $ $ Find the roots $\rm\ x\equiv a\pmod{\!5}.\,$ Substitute $\rm\ x = a + 5\:\! y\ $ into the equation yielding $\rm\ 10(1\! -\! a^2)\, y + a^3\!+\! 2a\!+\! 2\equiv 0\pmod{\!25}.\, $ Now check which roots $\rm\:a\:$ yield solutions for $\rm\:y.\:$

Remark $ $ This is a special case of a generalization of Newton's iterative method (Hensel's Lemma) for lifting roots of congruences $\rm \!\bmod p\,$ to roots $\rm\!\bmod p^k$. But you don't need to know anything about this method to solve the problem by using the above hint. But you should learn it asap.