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.

Solve the following equation: $ x^5 \equiv 7 \pmod {13}$

I think I need to raise both sides of the equation to some power, but I am not sure how to proceed.. Thanks in advance.

share|improve this question
add comment

4 Answers 4

You can just brute force this!

The number $13$ is small enough for you to try all of $1^5, 2^5, ..., 12^5$ and see which ones give you $7$.

Alternatively notice that by Fermat's little theorem $a^{12} \equiv 1$ mod $13$ (for $a$ coprime to $13$) so that raising both sides of your congruence to the multiplicative inverse of $5$ mod $12$ will get you $x$.

This inverse is actually again $5$ mod $12$ so that $x\equiv 7^5 \equiv 11$ mod $13$

share|improve this answer
1  
Fermat's little Theorem? Andrew Wiles just sent me a telegram saying he is angry with you! : D –  user21436 Feb 26 '12 at 14:17
    
+1 for FLT! :-) –  user21436 Feb 26 '12 at 14:18
    
Ha ha, I like cracking nuts with sledgehammers :p –  fretty Feb 26 '12 at 14:18
    
Edited lol, ten guesses what I was reading about before I wrote this? –  fretty Feb 26 '12 at 14:19
2  
Correct me if I'm wrong here, but isnt $7^5\equiv 11\mod 13$? –  Alex Becker Feb 26 '12 at 14:29
show 1 more comment

Note that certainly $x\not\equiv 0\mod 13$. An easy way to proceed is to observe that $$x^5\equiv 7\mod 13\iff x^{5\cdot5}\equiv 7^{5}\mod 13$$ because the map $y\to y^{5}$ is a bijection (since $5$ is coprime to $12$), and that $$x^{5\cdot 5}\equiv x^{24}x\equiv x\mod 13$$ $$7^5\equiv (-3)^2\cdot7\equiv11\mod 13$$ so we have $x\equiv 11\mod 13$.

share|improve this answer
    
I don't get why $x^{24}\equiv (-3)^2\mod 13$. –  Gigili Feb 26 '12 at 14:38
    
They aren't, but rather $x^{24}\equiv 1\mod 13$ because $y^{12}\equiv 1\mod 13$ for any $y$. The only reason I have two $\equiv$ in the second of the two equations is to show you how I got $7^5\equiv 11\mod 13$. I've edited to clarify. –  Alex Becker Feb 26 '12 at 14:43
    
Got it, thank you. –  Gigili Feb 26 '12 at 14:48
add comment

Hint $\ $ It is easy to compute a $\rm J$'th root of $\rm A$ in a group $\rm G$ if $\rm J $ is coprime to $\rm |G| = N.$

$\rm\phantom{\quad\Rightarrow}\quad\ A = X^J,\ \ X^N = 1 = A^N,\ \ (J,N) = 1\ \Rightarrow\ JK-NM = 1\ $ for $\rm\:K,M\in \mathbb Z$

$\rm\quad\Rightarrow\ \ A^{K} = X^{JK} = X^{1+NM} = X\: (X^N)^{M} = X$

$\rm\quad\Rightarrow\ \ X^{J} = A^{JK} = A^{1+NM} = A\: (A^N)^{M} = A$

In your case one has $\rm\:N = \phi(13) = 12,\:$ and $\: 5\cdot 5 - 12\cdot 2 = 1\:$ via extended Euclidean algorithm.

share|improve this answer
add comment

You might want to check out Hensel's lifting lemma.

share|improve this answer
1  
How will that work here? We are working mod a prime, not a power of a prime. –  fretty Feb 26 '12 at 20:33
add comment

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.