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.

$\endgroup$

4 Answers 4

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

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

$\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, 2012 at 14:17
  • $\begingroup$ Ha ha, I like cracking nuts with sledgehammers :p $\endgroup$
    – fretty
    Feb 26, 2012 at 14:18
  • $\begingroup$ Edited lol, ten guesses what I was reading about before I wrote this? $\endgroup$
    – fretty
    Feb 26, 2012 at 14:19
  • 2
    $\begingroup$ Correct me if I'm wrong here, but isnt $7^5\equiv 11\mod 13$? $\endgroup$ Feb 26, 2012 at 14:29
  • $\begingroup$ Yes, I was working mod $12$ lol, I will edit again :p $\endgroup$
    – fretty
    Feb 26, 2012 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.

$\endgroup$
0
$\begingroup$

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

$\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, 2012 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.