Why does modular exponentiation always form a cycle?

Question

I am not sure my question is linguistically precise with regards to mathematics. I will illustrate what I mean with an example.

Consider $2^i \pmod{15}$.

$2^0 = 1 \pmod{15}$
$2^1 = 2 \pmod{15}$
$2^2 = 4 \pmod{15}$
$2^3 = 8 \pmod{15}$
$2^4 \equiv 1 \pmod{15}$
$2^5 \equiv 2 \pmod{15}$
$2^6 \equiv 4 \pmod{15}$
$2^7 \equiv 8 \pmod{15}$
$2^8 \equiv 1 \pmod{15}$
$\vdots$

In this example, $2^i \pmod{15} \in \{1, 2, 4, 8\}$ for $i \geq 0$. It is true, in general, that for positive integers $a$, $b$, $n$, we have $a^b \pmod n$ is a cycle of a particular sequence.

Why?

As a follow up: is there any reason that $2^i \pmod{15}$ is a cycle of $\{1, 2, 4, 8\}$? Is there any reason that the numbers in a particular sequence are the ones that they are?

As a note, I have not studied group theory.

Answer 1

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

Answer 2

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.

Answer 3

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

1. $(a_n)$ is eventually cyclic (meaning that aside from the first few terms it is cyclic)
2. $(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$.
3. 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.