# If $g$ is a primitive root, show that $a$ is a $d$th power $\iff$ $a\equiv g^{kd}$

I wanted to ask you to help me with this exercise in numer theory. Here it is:

If $g$ is a primitive root modulo $p$ and $d|p-1$, show that $g^{(p-1)/d}$ has order $d$. Show also that $a$ is a $d$th power iff $a \equiv g^{kd} \; \text{mod}\,p$ for some $k$.

No problem for the first part, which is obvious, but I get stuck in showing the part concerning the $d$th power. Can you help me?? Thank you!!

• We know, ord$_ma=d,$ ord$_m(a^k)=\dfrac d{(d,k)}$ (Proof @Page#95) – lab bhattacharjee Aug 20 '14 at 9:43
• If $a$, coprime to $p$, is a $d$th power modulo $p$, then $a\equiv b^d$ for some $b$. Because $g$ is a primitive root, $b=g^k$ for some $k$. Therefore... Conversely, $g^{kd}=(g^k)^d$. – Jyrki Lahtonen Aug 20 '14 at 20:39

So given a primitive root $g$, you want to show that a number $a$ is a $d$th power if and only if $a \equiv g^{kd} \pmod p$.
Suppose that $a \equiv g^{kd}$. Then in particular, $a \equiv (g^k)^d$, and so $a$ is a $d$th power.
Conversely, if $a$ is a $d$th power, then $a \equiv m^d$ for some $m$. Since $g$ is a primitive root, $m \equiv g^k$ for some $k$. But then $a \equiv m^d \equiv g^{kd}$. So we've proven the claim. $\diamondsuit$