# Showing that $k | 12$ given $k$ is the order of $2$ mod $13$.

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.

• 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$. – André Nicolas Sep 17 '15 at 0:46
• Thank you so much. That is a crystal clear proof. – letsmakemuffinstogether Sep 17 '15 at 0:51
• You are welcome. Since you also had another question, and I wanted to amplify the above comment a little, I wrote an answer. – André Nicolas Sep 17 '15 at 1:01

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