# 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 think Hensel's lemma may be useful here. – yunone Mar 11 '11 at 6:48
• You've shown that there are no solutions which are 1 modulo 5, but a solution could also be 3 modulo 5, so you should also try things of the form $3+5k$. Hensel's lemma essentially does this calculation in complete generality, resulting in a formula for $k$ (when a valid $k$ exists). – Anton Geraschenko Mar 11 '11 at 7:03
• x=13 is the only solution. – Kerry Mar 11 '11 at 7:07
• @user7887: Could you solve me how to do it? Thank you. – Chan Mar 11 '11 at 7:26
• @Anton Geraschenko: Thank you. – Chan Mar 11 '11 at 7:29

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.

• @user7887: I haven't learned Hensel's Lemma yet, but from googling I saw there are three cases. Could you explain why $f'(1) = 0$ should be cast aside? I don't get it. – Chan Mar 11 '11 at 7:28
• Hi, this is the first application of it to me as well. Hensel's lemma says "..also, if $f'(r)=0$(mod p) and $f(r)\not=0$ (mod $p^{k}$), then $f(x)=0$ has no solution for $x=r$(mod $p^{k-1}$)". For a general good introduction of it, I recommend Serre's A course in arithmetic. – Kerry Mar 11 '11 at 7:32
• I edited to make it more clear. I used the statement in here:en.wikipedia.org/wiki/Hensel's_lemma – Kerry Mar 11 '11 at 7:33

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\ (mod\ 5)\:.\:$ Substitute $\rm\ x = a + 5\ y\$ into the equation yielding $\rm\ 10\ (1 - a^2)\ y + a^3+ 2\ a+ 2\equiv 0\ (mod\ 25)\:.\:$ Now check which roots $\rm\:a\:$ yield solutions for $\rm\:y\:.\:$

REMARK $\$ This is a special case of a general method due to Hensel for lifting solutions of congruences $\rm\:(mod\ p)\:$ to $\rm\:(mod\ p^n)\:$. However you don't need to know anything about this method to solve the problem using the above hint.