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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communitySolve 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$.
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$
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.