Cuando es válido $a^n \equiv a^{(n \;\bmod \; \varphi(m))} \pmod m$

Question

Qué condiciones en $a,m \in \mathbb{N}$ son necesarios para la fórmula $$a^n \equiv a^{(n \;\bmod \; \varphi(m))} \pmod m \tag{*}.$$ para ser válida, donde $\varphi$ es el de Euler totient función?

Por el teorema de Euler (*) es válida, si $\gcd(a,m)=1$, y el ejemplo de mi respuesta) $$2^{1002} \equiv 2^{(1002 \;\bmod \; 332)} \equiv 2^6 \equiv 64 \pmod{1002}$$ demuestra que sigue siendo válida para algunos $a,m$ $\gcd(a,m)\ne1.$ Aquí es un contra-ejemplo: $$2^{14} \equiv 4 \pmod 6, \quad\text{pero}\quad 2^{(14 \, \bmod \,\phi(6))} \equiv 2^{(14 \, \bmod \,2)} \equiv 2^0 \equiv 1 \pmod 6$$

Answer 1

El principal problema es que el $a^{\varphi(m)}\equiv a^0=1$ siempre falla cuando $\gcd(a,m)\neq1$. Por lo tanto, usted siempre va a ejecutar en problemas al $\gcd(a,m)\neq1$ y el exponente $n\bmod \varphi(m)$ sucede a reducir a$~0$. El problema no se limita a los exponentes$~0$ a pesar de que, ya que uno también, por ejemplo, $p^{1+\varphi(p^k)}\not\equiv p\pmod{p^k}$ primer $p$ y cualquier $k\geq2$. A través del teorema del resto Chino este fenómeno puede aparecer para algunos de los "componentes" de $n$ y no para otros. Así que lo que usted necesita es una especie de remainer operación de modulo$~\varphi(m)$, pero que no desciende por debajo de la más grande de la multiplicidad de un factor principal en el$~m$.