Is modular exponentiation always cyclical?

Question

In RSA clock arithmetics is used, and as Fermat's little theorem says, $a^p \bmod p = a$. The exponentiation is cyclical, $a^x = a^{x \bmod p-1} \bmod p$, the same sequence of numbers is repeated in each cycle. Is there in a similar way a cycle for all modular exponentiation, or, only for some cases like prime modulo?

Answer 1

Yes, if $\gcd(a,n)=1$. Otherwise, we still reach a cycle, but it might not get back where it started.

For all integers $n>0$, $a$, $x$

• when $\gcd(a,n)=1$, it holds $a^x\equiv a^{(x\bmod\lambda(n))}\pmod n$. The sequence $a_j$ defined as $a_0=1$, $a_{j+1}=a\cdot a_j\bmod n$ loops back at $1$, then $a\bmod n$.
  $\lambda$ is the Carmichael function, with $1\le\lambda(n)<n$ for all $n>1$.
  The smallest period of $a_j$ depends on $a$ and $n$. It it some divisor of $\lambda(n)$, called the order of $a$ modulo $n$. It is $1$ when $a\equiv1\pmod n$. It is $2$ for $a=n-1$ and $n>1$.
• when $\gcd(a,n)\ne1$, the sequence $a_j$ is ultimately periodic with a period dividing $\lambda(n)$, but the head of the sequence might not be part of the period. E.g. $a=2$, $n=12$, $a_0=1$, $a_1=2$, $a_2=4$, $a_3=8$, $a_4=4$.