Why does modular exponentiation always form a cycle?
Recall the property of remainders:
If $a\equiv a'\pmod{n}$ and $b\equiv b'\pmod n$, then $ab\equiv a'b' \pmod {n}$.
Since there are only finitely many remainders in $\mod n$, there exists a repetition.
Suppose $a^k \equiv r \pmod {n}$ and $a^l\equiv r\pmod{n}$, then $$a^{l+1}\equiv a^la\equiv ra\equiv a^ka \equiv a^{k+1}\pmod{n}$$
Since there are only finitely many elements in $\mathbb{Z}_n$ the sequence of powers of any element $a$ must reach a duplicate, so it must enter a cycle. If $a$ and $n$ are relatively prime that cycle will have to reach the starting point $a^0 \equiv 1$.
There is no
reason that the numbers in a particular sequence are the ones that they are.
Let's generalize a bit first.
In general, if $X$ is a finite set, $f:X\to X$ a function, and $a\in X$ an element, then define the sequence $a_n = f^n(a)$, where power here means $f$ composed with itself $n$ times. Writing this recursively, the definition is $a_0=a$, $a_n = f(a_{n-1})$.
Then
- $(a_n)$ is eventually cyclic (meaning that aside from the first few terms it is cyclic)
- $(a_n)$ is cyclic if and only if there is some $N>0$ such that $a_N=a_0=a$, in which case the period is the least such $N$.
- If $f$ is bijective, then $(a_n)$ is cyclic.
Proof.
Since $(a_n)$ is infinite, and $X$ is finite, by pigeonhole principle, some value in $(a_n)$ occurs twice. Say $a_i=a_j$, $i < j$. WLOG $i$ is the least index such that $a_i$ occurs at least twice in the sequence, and $j$ is the least index greater than $i$ such that $a_j=a_i$.
Then we want to show $(a_n)$ is cyclic starting at $a_i$ to prove 1. Let $N=j-i$. We'll show that for all $k\ge i$, $a_{k+N}=a_{k}$, which will prove our periodicity claim. $$a_{k+N} = f^{k+N}(a) = f^{k-i}(f^{i+N}(a))=f^{k-i}(f^j(a))=f^{k-i}(a_j)=f^{k-i}(a_i)=a_k. $$
Then 2. follows from the proof of 1. note that in the proof of 1., $i$ was the least index such that the value of $a_i$ occurred at least twice. Therefore all the entries in the sequence prior occurred only once, and were thus not part of any cycle. Thus the sequence $(a_n)$ is cyclic if and only if $i=0$, if and only if there is some $N>0$ such that $a_N=a_0=a$. Then if $i=0$, and $j$ is the least such $N$, as in the proof of 1., the proof of 1. shows that the period is $j-i=j-0=j$, as desired.
Finally 3. follows from 2. We'll prove that $i=0$, where $i$ again was the least index such that the value of $a_i$ occurred at least twice. Let $j > i$ be such that $a_j=a_i$. Then $f(a_{j-1})=a_j=a_i$. If $i>0$, then $f(a_{i-1})=a_i$. Then by injectivity of $f$, we have $a_{j-1}=a_{i-1}$ contradicting minimality of $i$. Thus $i=0$ if $f$ is bijective. $\blacksquare$
Applying this to your problem
How does this relate to your particular problem.
Well, suppose $X=\Bbb{Z}/m\Bbb{Z}$, $b\in \Bbb{Z}/m\Bbb{Z}$, then let $f:X\to X$ be defined by $f(x)=ax$. If we take $a=1$, the sequence $a_n$ we get is now $b^n \pmod{m}$, which is the sequence you care about.
Then the theorem says that the sequence is always eventually cyclic, and it is cyclic if and only if there is some $N > 0$ such that $b^N \equiv 1 \pmod{m}$. You can check that this means that it is cyclic if and only if $\gcd(b,m)=1$. This is because the function $f$ is invertible if and only if $b$ is a unit mod $m$, if and only if $\gcd(b,m)=1$.
Which numbers show up is more complicated, and I don't have an answer to that question right now.
Side note
The generalization allows us to prove even cooler things. For example: The Fibonacci sequence is always cyclic mod $n$.
Proof: Here let $X= \Bbb{Z}/n\Bbb{Z} \times \Bbb{Z}/n\Bbb{Z}$. Define $f:X\to X$ by $f(a,b)=(a+b,a)$. Let $a=(1,0)$. Then you can check that $f^i(a) \equiv (F_{i+1},F_i) \pmod{n}$. Therefore the sequence of values $f^i(a)$ is eventually periodic, but the values of $f^i(a)$ are pairs of Fibonacci numbers mod $n$, so if we pick out the second number in each pair, we've proved that the Fibonacci numbers mod $n$ are themselves eventually periodic.
However, $f$ is in fact invertible, with inverse $g(a,b) = (b,a-b)$. Therefore the sequence $f^i(a)$ is periodic, so the Fibonacci numbers mod $n$ are periodic.