Solution to $x^n=a \pmod p$ where $p$ is a prime Let $\gcd(a,p)=1$ where $p$ is prime, and let $n>0$. Prove that the congruence equation $x^n=a \pmod p$ has a solution if and only if $ordp(a)|\frac{(p-1)}{\gcd(n,p-1)}$.
Here, $ordp(a)$ denotes the order of $[a]$ in the field $(F_p)^*$
What I have so far:
Since $p$ is prime, the group $G=(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic. Therefore, 
$G^n=\{x^n : x \in G\} = <g^n> = <g^k>$ where $k=\gcd(m,n)$ where $m$ is order of $G$. 
In this case, $m=p-1$ so $k=\gcd(p-1,n)$
I don't know how to proceed further however. Any help would be appreciated!
 A: Let $g$ be a generator of the multiplicative group, and let $a=g^s$. We are trying to find a number $e$ between $1$ and $p-1$ such that $(g^e)^n=g^s$.
So we want $g^{en}\equiv g^s\pmod{p}$. This holds if and only if $en\equiv s\pmod{p-1}$. 
Now consider the congruence $en\equiv s\pmod{p-1}$, where $e$ should ne considered variable. This congruence has a solution if and only if $\gcd(n,p-1)$ divides $s$.
We therefore want to show that $\gcd(n,p-1)$ divides $s$ if and only if 
the order of $a$ divides $\frac{p-1}{\gcd(n,p-1)}$.
We will do one direction in detail, and leave the other direction to you. We show that  if $\gcd(n,p-1)$ divides $s$, then the order of $a$ divides $\frac{p-1}{\gcd(n,p-1)}$.
It is enough to show that $a$ raised to the power $\frac{p-1}{\gcd(n,p-1)}$ is congruent to $1$ modulo $p$. So we want to show that $g^s$ raised to the power $\frac{p-1}{\gcd(n,p-1)}$ is congruent to $1$ modulo $p$. To do this we need to show that $s\cdot \frac{p-1}{\gcd(n,p-1)}$ is a multiple of $p-1$. 
This is obvious. For we are told that $\gcd(n,p-1)$ divides $s$, say $s=a'\gcd(n,p-1)$. Then 
$$s\cdot \frac{p-1}{\gcd(n,p-1)}=s'\gcd(n,p-1)\cdot \frac{p-1}{\gcd(n,p-1)}=s'(p-1),$$
and $s'(p-1)$ is a multiple of $p-1$.
