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.

Improve this question
$\endgroup$
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't get why $x^{24}\equiv (-3)^2\mod 13$. $\endgroup$ – Gigili Feb 26 '12 at 14:38
  • $\begingroup$ 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. $\endgroup$ – Alex Becker Feb 26 '12 at 14:43
6
$\begingroup$

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$

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

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ How will that work here? We are working mod a prime, not a power of a prime. $\endgroup$ – fretty Feb 26 '12 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.