Show $k\mid 12$ with $2^k=1\bmod 13$ Let $k$ be the smallest positive integer such that $2^k=1\bmod 13$. Show that $k\mid 12$.
I'm not very good at proofs and I'm confused as how to prove this. I started by saying $2^k-1=13n$. But I don't know where to go from there.
 A: a few hints:


*

*pigeonhole-principle 

*Euler's totient function

A: Because by Fermat little theorem $2^{12}\equiv1(\mod13)$ 
and $2^n\equiv1(\mod13)$ is not true for all natural $n$ such that $1\leq n\leq11$. 
A: It seems quicker just to show directly that $k=12$.
Powers of $2 \bmod 13$: 
$\begin{array}{c|rl|l}
k &2^k &\bmod 13 & \text{using -ve}\\ \hline
1 && 2 \\ 2 && 4 \\ 3 && 8 \\
4 & 16\equiv\! & 3 \\
5&& 6 \\ 6&& 12 &\equiv -1\\ 
7 & 24\equiv\! & 11 &\equiv -2 \leftarrow 2^6\cdot 2^1\\
8 &  22\equiv\! &9 &\equiv -4 \leftarrow 2^6\cdot 2^2 \\
9 & 18\equiv\! &5 &\equiv -8 \leftarrow 2^6\cdot 2^3 \\
10 && 10  &\equiv -3 \leftarrow 2^6\cdot 2^4 \\ 
11 & 20\equiv\! & 7  &\equiv -6\\ 
12 & 14\equiv\! &1 &\equiv -(-1)
\end{array}$
The shortcut for negative equivalence values in the second half of the cycle also shown. This demonstrates that finding $p{-}1$ must indicate the halfway point of the cycle.
A: $$
\begin{array}{c|c}
\hline
i & \text{ $2^i $ mod 13} \\
\hline
  1&2 \\
  2&4 \\
  3&8 \\
  4&3 \\
  5&6 \\
  6&12 \\
  7&11 \\
  8&9 \\
  9&5 \\
  10&10 \\
  11&7 \\
  12&1 \\
\hline
\end{array}
$$
First, for $0 \le k \le 12$, only $2^{12} \equiv 2^0 \equiv 1 \quad mod(13)$
Assume $k=12i+j$, where $0 \le j < 12$, then
$$2^k \equiv 2^{12i+j} \equiv 2^{12i} \cdot 2^j \equiv 1\cdot 2^j \equiv 1 \quad mod(13)$$
So $2^j=1$, $j=0$, and $k=12i, k|12$
(smallest positive integer of k is 12, obviously)
