<s>[INST] Show that $x^d \equiv a$ mod $p$ if and only if $a^\frac{p-1}{d} \equiv 1$ mod $p$ Let $p$ be an odd prime and $d$ be a natural number such that $d \mid (p-1)$. For $a \in Z$ coprime with p, show that $x^d \equiv a$ mod $p$ if and only if $a^\frac{p-1}{d} \equiv 1$ mod $p$. I have no idea about this $x^d \equiv a$ mod p.
 [/INST] Assumptions:


*

*$p$ is prime.

*$d$ is a positive integer such that $d \mid (p-1)$. 

*$a$ is an integer, $a$ not a multiple of $p$.


To be shown: 


*

*$x^d \equiv a \pmod{p}$, for some integer $x$, if and only if $a^\frac{p-1}{d} \equiv 1 \pmod{p}$.



First we show $x^d \equiv a \pmod{p}$, for some integer $x$, implies $a^\frac{p-1}{d} \equiv 1 \pmod{p}$.

Thus, suppose there is an integer $x$ such that $x^d \equiv a \pmod{p}$.

Since $a,p$ are relatively prime, $x^d \equiv a \pmod{p}$ implies $x,p$ are relatively prime.

Then
\begin{align*}
a^\frac{p-1}{d} &\equiv (x^d)^\frac{p-1}{d} \pmod{p}\\[6pt]
&\equiv x^{p-1} \pmod{p}\\[6pt]
&\equiv 1 \pmod{p}\\[6pt]
\end{align*}
as was to be shown.

Next we show $a^\frac{p-1}{d} \equiv 1 \pmod{p}$ implies $x^d \equiv a \pmod{p}$, for some integer $x$.

Thus, suppose $a^\frac{p-1}{d} \equiv 1 \pmod{p}$.

Since $p$ is prime, there exists a primitive element, mod $p$. Let $y$ be such an element.

Since $y$ is a primitive element, mod $p$, the multiplicative order, mod $p$, of $y$ is $p-1$.

It follows that the $p-1$ elements $1,y,y^2,...y^{p-2}$ represent, in some order, all nonzero residues, mod $p$. In particular, there is an integer $k \in \{0,1,...,p-2\}$ such that $y^k \equiv a \pmod{p}$.

Then
\begin{align*}
&a^\frac{p-1}{d} \equiv 1  \pmod{p}\\[6pt]
\implies\; &(y^k)^\frac{p-1}{d} \equiv 1  \pmod{p}\\[6pt]
\implies\; &(p-1)\; \text{ divides} \left(k{\small{\left(\frac{p-1}{d}\right)}}\right)\\[6pt]
\implies\; 
&
{\frac
{k{\large{\left(\frac{p-1}{d}\right)}}}
{p-1}} \in \mathbb{Z}^+
\\[6pt]
\implies\; &{\frac{k}{d}} \in \mathbb{Z}^+\\[6pt]
\implies\; &k = jd,\text{ for some }j \in \mathbb{Z}^+\\[6pt]
\end{align*}
Let $x = y^j$. Then
\begin{align*}
x^d &\equiv (y^j)^d \pmod{p}\\[6pt]
&\equiv y^{jd} \pmod{p}\\[6pt]
&\equiv y^k \pmod{p}\\[6pt]
&\equiv a \pmod{p}\\[6pt]
\end{align*}
thus, we have an integer $x$ such that $x^d \equiv a \pmod{p}$, as was to be shown.
This completes the proof.
</s>