For $a$, $m$ fixed with $a \lt m$ and $r$ a nonnegative integer, I was wondering what the period of $f(r) = a^r$ mod $m$ was. For example, when $a=2, m=7$, we get the sequence 1, 2, 4, 1, 2, 4,... with a period of 3. Because there are at most $m$ values that $f$ takes on, it follows that the function must be periodic. I looked at Euler's theorem, but $\phi(n)$ seems to be some multiple of the period.
$\endgroup$ 01 Answer
$\begingroup$Look-up the concept of multiplicative order. You have $a^{\mathrm{ord}_m(a)}=1$ or $a^{1+\mathrm{ord}_m(a)}=a.$ Accidently the Wiki article even uses your $m=7.$ The order devides $\phi(m)$ and even the Carmichael function function $\lambda(m)$.
For algorithms to compute the multiplicative order if the prime factorizations of $\phi(m)$ or $\lambda(m)$ are known, see my answers to: Algorithms for finding the multiplicative order of an element in a group of integers mod mand algorithm to find the order of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$ where $n$ is not prime.
$\endgroup$
