Let a,n be positive integers with gcd(a,n)=1. Show that if $x^k \equiv a \ (mod \ n)$ has a solution, then $a^{ \phi / d } \equiv 1 \ (mod \ n)$, where d = gcd ( $\phi (n) , k$ ).
Note: $\phi (a)$ denotes the number of positive integers less than a that are relative prime to a.
2. I think you forgot to mention the important detail. If $n$ has a primitive root ...