1

I'm trying to solve

$$ 2^x \equiv 9 \pmod{13} $$

so I tried to define all numbers for $x$ which match this requirement and I came up with this equation:

$$ \sqrt{\sin(((x)-13/2-9)*\pi/13)^2} $$

now i just want numbers 2^x and i changed it to

$$ \sqrt{\sin(((2^x)-13/2-9)*\pi/13)^2} = 1 $$

this part seems to work, i come to

$${pi = pi, x = ln(-1/2*(-31*pi+13*Pi)/pi)/ln(2)}, {pi = pi, x = ln(1/2*(31*pi+13*Pi)/pi)/ln(2)}$$

and

$$ 2^(1.442695041*ln(-.5000000000*(-31.*pi+40.84070450)/pi)) = 9.00000000099 $$

the second requirement is that $x$ is an integer, I defined it by this equation

$$ \sqrt{\sin((x+1/2)*\pi)^2}=1 $$

but when I try to solve this system of equations with maple, I don't get an answer, why?

wutzebaer
  • 147
  • 2
  • 10

3 Answers3

7

The powers of $2$ mod $13$ are: $$ \begin{array}{c|c} n&0&1&2&3&4&5&6&7&8&9&10&11&12\\ \hline 2^n\text{ mod }13&1&2&4&8&3&6&12&11&9&5&10&7&1 \end{array} $$ Note that this repeats for $n$ mod $12$. Therefore, $$ n\equiv8\pmod{12}\implies2^n\equiv9\pmod{13} $$

Here are plots of the functions you are using:

$\hspace{8mm}$enter image description here

Both curves do seem to meet at $x=8$; however, tangents to solutions are often less stable for automated solvers. A small amount of error can keep a solution from being found. This is most likely why Maple is having trouble finding solutions. The frequecy of the green function get higher as $x$ gets larger, while the frequency of the red function stays constant. This also adds to the numerical instability.

A more stable attempt would be to use $$ \sin((2^x-9)\pi/13)=0 $$ and $$ \sin(x\pi/13)=0 $$ enter image description here

However, the frequency of the green function becomes so great at the next solution ($x=20$), that numerical solution become sensitive to small errors because of that.

robjohn
  • 345,667
  • i know the brute force way... the question was what's wrong with my equations? – wutzebaer Sep 15 '13 at 20:47
  • 2
    The question is: What's right about them? How do you justify them? – Servaes Sep 15 '13 at 20:47
  • you can plot them... the maximum points of the first equation are the solutions for x mod 13=9 – wutzebaer Sep 15 '13 at 20:51
  • Is there a more general theorem at use here to show that $n \equiv a \space \left( \text{mod } b \right)$ implies $2^n \equiv c \space \left( \text{mod } d \right)$? – Ryan Sep 15 '13 at 23:37
  • @Ryan: Yes. If $n\equiv a\pmod{\phi(13)}$, then $2^n\equiv2^a\pmod{13}$ – robjohn Sep 16 '13 at 13:16
  • hm and why isn't there a solution for this system of equations? $sin((2^x-9)Pi/13)=sin(xPi)$ is no problem, but the combination with $sin(x*Pi)=0$ ... – wutzebaer Sep 17 '13 at 18:02
  • @wutzebaer: My guess is that it is because you are trying to find the intersection of three curves in $\mathbb{R}^2$. That is fraught with trouble if there is any error. – robjohn Sep 17 '13 at 19:32
1

I used another method, using less intelligence than Mark Bennet's answer but still a little quicker than checking all the powers until the answer appears. Checking powers of 2 modulo 13, I got 2, 4, 8, 3, 6, 12. Since $2^6\equiv 12\equiv-1$ and $2^2=4$, it follows that $2^{6+2}\equiv4\cdot(-1)\equiv 9$ so one solution is 6+2, i.e., 8.

To get all the solutions, use the fact that powers of 2 (or of anything) repeat after 12 steps, by Fermat's little theorem. The powers of 2 don't repeat after any proper divisor of 2 many steps (because none of the 2, 4, 8, 3, 6, 12 computed above are 1), so all the solutions are $8+12k$ for arbitrary natural numbers $k$.

Andreas Blass
  • 71,833
0

Note that $2^4=16 \equiv 3 \mod 13$ so that $2^8=(2^4)^2\equiv (3)^2=9 \mod 13$

Mark Bennet
  • 100,194
  • this only works if i already know that the result is 8 – wutzebaer Sep 15 '13 at 20:38
  • 1
    @wutzebaer I didn't know what the answer was, and I have written down how I worked it out. If I didn't spot a short cut, I could compute all the powers of $2$ modulo $13$: $2^0=1, 2, 4, 8, 3, 6, 12, 11, 9$ until I got to $9$. It is not guaranteed that there will be a solution, but since we know from Fermat that $2^{12} \equiv 1$ we know that we have a finite task - and in fact when $2^4$ and $2^6$ turn out not to be $1$ we know that $2$ is a primitive root mod 13, and there will be a solution. – Mark Bennet Sep 15 '13 at 20:44
  • means i just need to find an $2^x$ whichs result is an divider of the wanted result? – wutzebaer Sep 15 '13 at 20:58