Prueba de $a^{m \, \pmod{\varphi(n)}} \equiv a^m\pmod n$

Question

Actualmente estoy estudiando aritmética modular para un curso de criptografía. He demostrado muchas operaciones, pero estoy atascado en una:

Supongamos $n,a\in \mathbb{N}$ y $n\ge 2$. Demuestra que si $\gcd(a,n)=1$ entonces:

$$a^{m \, \pmod{\varphi(n)}} \equiv a^m\pmod n$$

donde $\varphi$ es la función de Euler.

Estoy seguro de que tengo que usar el teorema de Euler:

Si $n,a\in \mathbb{N}$ y $n\ge 2, \gcd(a,n)=1$ entonces:

$$a^{\varphi(n)} \equiv 1 \pmod n$$

Puede ser obvio, pero no lo veo.

Gracias por tu ayuda.

Answer 1

Si $m=d+k\varphi(n)$, entonces $$ a^m=a^{d}(a^{\varphi(n)})^k\equiv a^d\mod n$$ ya que $a^{\varphi(n)}\equiv 1 \pmod n$. Y $m\equiv d \pmod{\varphi(n)}$, por lo que este es el resultado deseado.