Method of solving $x^5=2\pmod{13}$ and $x^3=2\pmod{11}$

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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?

Answer 4

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

Answer 5

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