Method of solving $x^5=2\pmod{13}$ and $x^3=2\pmod{11}$ I have the following equations :
$$x^5=2 \pmod {13}$$ $$x^3=2 \pmod{11}$$
I wonder how to solve such equations is there a method to get rid off the powers in order to use the Chinese Remainder Theorem without checking each $x$ value?
Any ideas?
Thank you.
 A: Hint: If $x^3\equiv 2\pmod{11}$ then $ x^{21}\equiv 2^7\pmod{11}$.
By Fermat, we have $x^{21}\equiv x\pmod{11}$.
A: ${\rm mod}\ 11\!:\ x^{\large 3\cdot 7} \equiv x\,\ $ by $\,\ x^{\large 1+2\cdot 10}\!\equiv x(x^{\large 10})^{\large 2}\!\equiv x(1)^{\large  2}\equiv  x\ $ by Fermat (clear if $\,x\equiv 0)$
therefore  $\ \  x^{\large 3}\equiv a\iff  x\equiv a^{\large 7}\ $
because  $\ \left[x^{\large 3} \equiv a\right]^{\large 7}\! \Longrightarrow\, x\equiv a^{\large 7}\ \ \,$ by $\,\ \ x^{\large 3\cdot 7}\equiv x$
because  $\ \ x^{\large 3}  \equiv a \  \Longleftarrow \ \left[ x\equiv a^{\large 7}\right]^{\large 3} $ by $\,\ a^{\large 7\cdot 3}\equiv a$
Remark $\ $ This is essentially the same way your would solve the equation in $\,\Bbb  R\,$ by raising $\,x^{\large 3}\,$ to the power $\, 1/3,\,$  but here $\,1/3\equiv 7\pmod{\!10},\,$ and powers can be considered mod $10$ by Fermat. Said functionally, $\,f(x) \equiv x^{\large 3}\,$ is injective $(1$-to-$1),\,$ with inverse $\,x^{\large 7},\,$ because the exponent $3$ is  invertible mod $\,p\!-\!1 = 10,\,$ being coprime to it.
A: There are simple techniques to check these, and you will find that
$$x^5\equiv2\pmod{13}\implies x=13n+6$$
$$x^3\equiv2\pmod{11}\implies x=11k+7$$
For the first, we assumed that $x=13n+a$ for each $a=0,\pm1,\pm2,\dots,\pm6$.  For the second, we assumed that $x=11k+b\mod11$ for each $b=0,\pm1,\pm2,\dots.,\pm5$. As these numbers form a complete residue system, it is sufficient to consider them.
A: we have $$1^5\equiv 1 \mod 13$$
$$2^5\equiv 6 \mod 13$$
$$3^5\equiv 9 \mod 13$$
$$4^5\equiv 10 \mod 13$$
$$5^5  \equiv 5 \mod 13$$
$$6^5 \equiv 2 \mod 13$$
can you proceed?
A: You can simplify the computations writing the elements in $\mathbf F_{13}$ and  $\mathbf F_{11}$ as
$$\{0,\pm 1,\pm 2,\pm3,\pm4,\pm 5,\pm6\}\quad\text{and}\quad\{0,\pm 1,\pm 2,\pm3,\pm4,\pm 5\}$$
respectively. As $0$ and $1$ can't be solutions, we only have this computation for the first equation:
$$\begin{array}{c*{7}{c}}
x&\pm2&\pm3&\pm4&\pm5&\pm6\\
\hline
x^2&4&-4&3&-1&-3\\
x^4&3&3&-4&1&-4\\
\hline
x^5&\pm6&\mp4&\mp3&\pm5&\pm2
\end{array}$$
Hence there is only one solution: $\;x=6$.
