Let a,n be positive integers with gcd(a,n)=1. Show that if $\displaystyle x^k \equiv a \ (mod \ n) $ has a solution, then $\displaystyle a^{ \phi / d } \equiv 1 \ (mod \ n) $, where d = gcd ( $\displaystyle \phi (n) , k $ ).

Note: $\displaystyle \phi (a) $ denotes the number of positive integers less than a that are relative prime to a.