Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
1  
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
1  
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

5 Answers 5

up vote 6 down vote accepted

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.

enter image description here enter image description here enter image description here enter image description here

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.

share|improve this answer
    
Many thanks, great answer ;). –  Chan Mar 12 '11 at 5:58

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.

share|improve this answer
    
@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

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$

share|improve this answer

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)$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.