How to prove periodicity Modulo b

Question

We have the sequence

$$ x_n=a^n \mod{b}, $$ where $a$ and $b$ are positive integers. How to show that it's periodic? It is intuitively clear but I have no clue how to prove it rigorously from first principles...

Thanks in advance

Answer 1

Using the fact that \begin{align} a^{\varphi(b)}\equiv 1 \mod b \end{align} and the fact that for any $n$ \begin{align} n = \varphi(b)k+r \end{align} for some $0\leq r<\varphi(b)$ we have the desired result. Here $\varphi(b)$ is the Euler Totient function.

Answer 2

Note first that periodic here means there are $K$, $P > 0$ such that $a^{i} = a^{i+P}$ for $i > K$.

One begins with showing that there are $m > n$ such that $a^{m} = a^{n}$. Then for all $i > n$ we have $$ a^{i} = a^{i - n + n} = a^{i - n} a^{n} = a^{i - n} a^{m} = a^{i + (m - n)}. $$ So you can take $K = n$ and $P = m - n$.