4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Have you checked to see how many numbers $x$ there are such that $x^5\equiv 2\pmod{13}$? $\endgroup$ – abiessu Dec 30 '16 at 17:00
  • $\begingroup$ @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. $\endgroup$ – JaVaPG Dec 30 '16 at 17:02
  • $\begingroup$ Hint: $(-x)^5=-(x^5)$. If my calculations are correct, there's only one solution to the first equation... $\endgroup$ – abiessu Dec 30 '16 at 17:03
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

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

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.

$\endgroup$
4
  • $\begingroup$ Can you explain why $x^5\equiv2\pmod{13}\implies x=13n+6$? how did you manage to reach to $6$ at $x=$? $\endgroup$ – JaVaPG Dec 30 '16 at 17:07
  • $\begingroup$ @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}$. $\endgroup$ – Simply Beautiful Art Dec 30 '16 at 17:09
  • $\begingroup$ @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. $\endgroup$ – abiessu Dec 30 '16 at 17:09
  • $\begingroup$ You don't need to use enumeration, since $5$ is relatively prime to $13-1$ and $3$ is relatively prime to $11-1$. $\endgroup$ – Thomas Andrews Dec 30 '16 at 17:09
0
$\begingroup$

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

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

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.