I would like to prove that the following 2 are equivalent:
$\gcd(a,n)=1$ and $\exists x: x^m\equiv a \pmod n$
$a^{\frac{\phi(n)}{d}}\equiv 1 \pmod n$ where $d=\gcd(m,\phi(n))$
$\phi(n)$ is Euler 's function.
I've proved $1\rightarrow 2$.
Any ideas on $2\rightarrow 1$?