Is there a formula for the periodicity of a^b mod n?

Question

I am looking for a formula for the minimum p for which $$Mod[a^{p+1},n]=a$$ for all $a<n$.

I am aware of Euler's formula, $Mod[a^{\phi(n)},n]=1$ when (a,n) are coprime, which implies that $Mod[a^{k\phi(n)+1},n]=a$. But I'm looking for the minimum periodicity that applies to all $a<n$ and the conditions under which such periodicity exists.

If n is prime, then Euler tells us that the periodicity is just EulerPhi[n] which is n-1.

But $n=15$ has a periodicity of 4 for all $a<15$ even though the EulerPhi[15]=8 and 15 is non-coprime with several a's. $Mod[a^{4k+1},15]=a$

And if $n=12$, no value of p works for $a\epsilon\{2,6,10\}$

So is there a general formula for determining the periodicity and whether it exists? I want to be clear that individual a's might have different periodicities, but I'm looking for lowest the p over which the entire set $a<n$ is periodic.

Answer 1

You are right, Eulers totient function $\varphi(n)$ is only an upper bound on the periodicity. The precise answer is given by the "Carmichael function" $\lambda(n)$, which is also sometimes called "reduced totient function". Check https://en.wikipedia.org/wiki/Carmichael_function for remarks on that. Your examples are totally correct:

1. For any prime $p$ it is $\varphi(p)=\lambda(p)=p-1$
2. For $n=15$ it is $\varphi(15)=8$ but $\lambda(15)=4$.

In terms of group theory, $\varphi(n)$ is the order of the group $(\mathbb{Z}/n\mathbb{Z})^*$, and $\lambda(n)$ is the exponent of the group $(\mathbb{Z}/n\mathbb{Z})^*$.