# How to find $x$ if $x^5 \equiv 7 \pmod {13}$

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.

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

• I don't get why $x^{24}\equiv (-3)^2\mod 13$. Feb 26, 2012 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. Feb 26, 2012 at 14:43

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$

• Fermat's little Theorem? Andrew Wiles just sent me a telegram saying he is angry with you! : D
– user21436
Feb 26, 2012 at 14:17
• Ha ha, I like cracking nuts with sledgehammers :p Feb 26, 2012 at 14:18
• Edited lol, ten guesses what I was reading about before I wrote this? Feb 26, 2012 at 14:19
• Correct me if I'm wrong here, but isnt $7^5\equiv 11\mod 13$? Feb 26, 2012 at 14:29
• Yes, I was working mod $12$ lol, I will edit again :p Feb 26, 2012 at 14:34

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.

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

• How will that work here? We are working mod a prime, not a power of a prime. Feb 26, 2012 at 20:33