1
$\begingroup$

I am trying to show that $k | 12$ given $k$ is the order of $2$ mod $13$. Is it sufficient if I use Euler's theorem like this: By Euler's theorem, since (2,13) = 1, we have it that $2^{\phi(13)} \equiv 1$ (mod 13) which implies that $2^{12} \equiv 1$ (mod 13). So certainly, $k$ divides 12. Is that right?

Also, I am trying to show that $2^{i} \equiv 2^{j}$ (mod 13) $\Leftrightarrow i \equiv j$ (mod 12) however I am unsure how to start. For instance, intuitively I want to use the logarithm rules but this is probably invalid in the context of modular arithmetic. I want to use Euler's theorem since $\phi(13 = 12$ however I am unsure how to connect the two implications.

$\endgroup$
  • 3
    $\begingroup$ Assume $i$ and $j$ are non-negative integers, and that $i\le j$. Then $2^i\equiv 2^j\pmod{13}$ if and only if $2^{j-i}\equiv 1\pmod{13}$. Since $2$ has order exactly $12$, we have $2^{j-i}\equiv 1\pmod{13}$ if and only if $12$ divides $j-i$. $\endgroup$ – André Nicolas Sep 17 '15 at 0:46
  • $\begingroup$ Thank you so much. That is a crystal clear proof. $\endgroup$ – letsmakemuffinstogether Sep 17 '15 at 0:51
  • $\begingroup$ You are welcome. Since you also had another question, and I wanted to amplify the above comment a little, I wrote an answer. $\endgroup$ – André Nicolas Sep 17 '15 at 1:01
1
$\begingroup$

First question: If already in your class or book, it has been proved that the order of any $a$ (relatively prime to $m$) divides $\varphi(m)$, then you can say, perhaps referring to this result, that certainly the order of $2$ divides $12$.

If you do not yet have such a theorem, then you can find the order of $2$ modulo $13$ by directly computing $2^1, 2^2, \dots$ modulo $13$ until you bump into $1$. It will turn out that the order of $2$ is exactly $12$. You will need that fact for the second question.

Second question: Assume $i$ and $j$ are non-negative integers, and that $i\le j$. Then $2^i\equiv 2^j\pmod{13}$ if and only if $2^{j-i}\equiv 1\pmod{13}$.
If you want to prove this, use the fact that if $a$ and $m$ are relatively prime, then $ax\equiv ay\pmod{m}$ if and only if $x\equiv y\pmod{m}$. Since $2$ has order exactly $12$, we have $2^{j-i}\equiv 1\pmod{13}$ if and only if $12$ divides $j-i$. An essentially identical argument takes care of the case $i\gt j$.

If you want to also deal with possibly negative integers $i$ and/or $j$, you will have to define what you mean by $2^{-k}$ for positive $k$. This can be done, but it is not the ordinary $2^{-k}$, it is the multiplicative inverse of $2^k$ modulo $13$.

$\endgroup$

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.