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

• Have you checked to see how many numbers $x$ there are such that $x^5\equiv 2\pmod{13}$? – abiessu Dec 30 '16 at 17:00
• @abiessu No, I don't know how many numbers are there, I just checked for $x=1,2,3,..$ until I got to the right $x$ yet for higher number I had to use a calculator which I can't use during an exam. – JaVaPG Dec 30 '16 at 17:02
• Hint: $(-x)^5=-(x^5)$. If my calculations are correct, there's only one solution to the first equation... – abiessu Dec 30 '16 at 17:03

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

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

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?

• Yes, Yet I'm looking for a method without checking for each $x$. – JaVaPG Dec 30 '16 at 17:15
• @JaVaPG look at Thomas' answer. He has provided a more elegant method. – IamThat Dec 30 '16 at 17:26

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.

• Can you explain why $x^5\equiv2\pmod{13}\implies x=13n+6$? how did you manage to reach to $6$ at $x=$? – JaVaPG Dec 30 '16 at 17:07
• @JaVaPG If $x=13n+6$, then $x^5=(13n+6)^5$. Can you expand this with the binomial theorem and then rewrite it so that you can see the result as $13p+2$? Thus, $x^5\equiv2\pmod{13}$. – Simply Beautiful Art Dec 30 '16 at 17:09
• @JaVaPG: you probably also want to consider the phrase "modular exponentiation", which can help in cases where a calculation of this nature is limited on resources. – abiessu Dec 30 '16 at 17:09
• You don't need to use enumeration, since $5$ is relatively prime to $13-1$ and $3$ is relatively prime to $11-1$. – Thomas Andrews Dec 30 '16 at 17:09

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

• Can you expand you'r solution how did you managed to solve from the first equation to the second? – JaVaPG Dec 30 '16 at 17:22
• ?? I only solved one equation. – Bernard Dec 30 '16 at 17:26