4
$\begingroup$

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.

4 Answers 4

7

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

  • 0
    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.2012-02-26
6

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$

  • 0
    Yes, I was working mod $12$ lol, I will edit again :p2012-02-26
3

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.

0

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

  • 1
    How will that work here? We are working mod a prime, not a power of a prime.2012-02-26