How to prove periodicity Modulo b 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
Note first that periodic here means there are $K$, $P &gt; 0$ such that $a^{i} = a^{i+P}$ for $i &gt; K$.

One begins with showing that there are $m &gt; n$ such that $a^{m} =  a^{n}$. Then for all $i &gt; 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$.
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&lt;\varphi(b)$ we have the desired result. Here $\varphi(b)$ is the Euler Totient function.