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.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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$.
answered Feb 26, 2012 at 14:28
-
$\begingroup$ I don't get why $x^{24}\equiv (-3)^2\mod 13$. $\endgroup$– GigiliFeb 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
$\begingroup$
$\endgroup$
5
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$
-
1$\begingroup$ Fermat's little Theorem? Andrew Wiles just sent me a telegram saying he is angry with you! : D $\endgroup$– user21436Feb 26, 2012 at 14:17
-
$\begingroup$ Ha ha, I like cracking nuts with sledgehammers :p $\endgroup$– frettyFeb 26, 2012 at 14:18
-
$\begingroup$ Edited lol, ten guesses what I was reading about before I wrote this? $\endgroup$– frettyFeb 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$– frettyFeb 26, 2012 at 14:34
$\begingroup$
$\endgroup$
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.
answered Feb 26, 2012 at 16:09
$\begingroup$
$\endgroup$
1
You might want to check out Hensel's lifting lemma.
answered Feb 26, 2012 at 17:05
-
1$\begingroup$ How will that work here? We are working mod a prime, not a power of a prime. $\endgroup$– frettyFeb 26, 2012 at 20:33