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!

Solution 1:

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$.