# Is modular exponentiation always cyclical?

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?

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) 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$$.
• Thanks, very good answer. Could I ask just in the context of trying to understand cyclical nature of modular exponentiation, is 𝜆(n) the point where the cyclical group for every integer a between 1 and n has looped? May 19, 2019 at 16:23
• "$a^x\equiv a^{(x\bmod\lambda(n))}\pmod n$ holds for all positive integers $a$, $x$, $n$"; counterexample: $a=2, x=2, n=4$ :-) May 19, 2019 at 17:06
• Ok it was in the answer already. I missed it, probably because I am learning and a lot to take in, jumping between this answer and Wikipedia. Thanks for helping me along the way. May 19, 2019 at 17:09
• @poncho: thanks for the correction.
– fgrieu
May 19, 2019 at 19:22