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$$

  • $\begingroup$ 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... $\endgroup$ – Ludolila Nov 13 '13 at 14:28
  • $\begingroup$ @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. $\endgroup$ – gammatester Nov 13 '13 at 14:39
  • $\begingroup$ Right, good point... =) I'll keep thinking... $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.