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

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 '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
Correct me if I'm wrong here, but isnt $7^5\equiv 11\mod 13$? – Alex Becker Feb 26 '12 at 14:29

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. – fretty Feb 26 '12 at 20:33