2
$\begingroup$

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!!

$\endgroup$
  • $\begingroup$ We know, ord$_ma=d,$ ord$_m(a^k)=\dfrac d{(d,k)}$ (Proof @Page#95) $\endgroup$ – lab bhattacharjee Aug 20 '14 at 9:43
  • $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Aug 20 '14 at 20:39
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.