# When is $a^n \equiv a^{(n \;\bmod \; \varphi(m))} \pmod m$ valid

What conditions on $a,m \in \mathbb{N}$ are needed for the formula $$a^n \equiv a^{(n \;\bmod \; \varphi(m))} \pmod m \tag{*}.$$ to be valid, where $\varphi$ is the Euler totient function?

By Euler's theorem (*) is valid, if $\gcd(a,m)=1$, and the example (from my answer) $$2^{1002} \equiv 2^{(1002 \;\bmod \; 332)} \equiv 2^6 \equiv 64 \pmod{1002}$$ shows that it remains valid for some $a,m$ with $\gcd(a,m)\ne1.$ Here is a counter-example: $$2^{14} \equiv 4 \pmod 6, \quad\text{but}\quad 2^{(14 \, \bmod \,\phi(6))} \equiv 2^{(14 \, \bmod \,2)} \equiv 2^0 \equiv 1 \pmod 6$$

• I am not sure, but I think it has something to do with the fact that $1002=2 * 3 * 167$ composed of primes with multiplicity $1$ (that is, there are no greater powers of primes such as $2^2$ etc.) So maybe it works due to this fact, combined with Fermat's little theorem... – Ludolila Nov 13 '13 at 14:28
• @Ludolila: I do not think your thought applies here because in the counter-example both 6=2*3 and 14=2*7 are square-free. – gammatester Nov 13 '13 at 14:39
• Right, good point... =) I'll keep thinking... – Ludolila Nov 13 '13 at 14:45

The main problem is that $a^{\varphi(m)}\equiv a^0=1$ always fails when $\gcd(a,m)\neq1$. Therefore you will always run into trouble when $\gcd(a,m)\neq1$ and the exponent $n\bmod \varphi(m)$ happens to reduce to$~0$. The problem is not limited to exponents$~0$ though, since one also has for instance $p^{1+\varphi(p^k)}\not\equiv p\pmod{p^k}$ for prime $p$ and any $k\geq2$. Through the Chinese remainder theorem this phenomenon may appear for some "components" of $n$ and not for others. So what you would need is a kind of remainer operation modulo$~\varphi(m)$, but which does not descend below the largest multiplicity of a prime factor in$~m$.