# Primitive roots as roots of equations.

Take $g$ to be a primitive root $\pmod p$, and $n \in \{0, 1,\ldots,p-2\}$ write down a necessary sufficient condition for $x=g^n$ to be a root of $x^5\equiv 1\pmod p$ . This should depend on $n$ and $p$ only, not $g$.

How many such roots $x$ of this equation are there? This answer may only depend on $p$.

At a guess for the first part I'd say as $g^{5n} \equiv g^{p-1}$ it implies for $x$ to be a root $5n \equiv p-1 \pmod p$. No idea if this is right and not sure what to do for second part. Thanks for any help.

-

Hint. In any abelian group, if $a$ has order $n$, then $a^r$ has order $n/\gcd(n,r)$.

(Your idea is fine, except that you got the wrong congruence: it should be $5n\equiv p-1\pmod{p-1}$, not modulo $p$; do you see why?)

For the second part, you'll need to see what you get from the first part. That will help you figure it out.

-
Thanks for help so far! Yeah I see it should be p-1 but still not sure on how many such roots. From your hint I think the answer is gcd(5, p-1) this shows how many n<p-1 have p-1|5n . For example p=101 would suggest there were 5 solutions and indeed 0, 20, 40, 60 and 80 are 5 such ones. Is this right? –  Mike Davies Apr 27 '12 at 20:55
@MikeDavis: No. $g^r$ has order $(p-1)/\gcd(r,p-1)$. You want this number to divide $5$, so you want this number to be either $1$ or $5$. So you are asking: for how many different $r$ is $(p-1)/\gcd(r,p-1)$ equal to $1$ or to $5$, $1\leq r\leq p-2$? This is equivalent to asking: for how many $n$ does $5n\equiv 0\pmod{p-1}$? Do you know how to count the number of solutions to $ax\equiv 0\pmod{k}$? –  Arturo Magidin Apr 27 '12 at 21:08
That makes sense but I thought number of solutions to $5n\equiv 0\pmod{p-1}$ is $gcd(5,p-1)$? Though sounds like I could be wrong? I think the answer can only be 5 or 1 though depending on the value of p, i.e. 5 if p is of the form 10k+1 and 1 otherwise? Thanks for your help so far, sorry I'm a bit slow on the uptake! –  Mike Davies Apr 27 '12 at 21:48
@MikeDavis: Sorry; I misunderstood your comment... Yes, you have that many solutions. The one who was slow there was me. –  Arturo Magidin Apr 27 '12 at 21:52
No bother, thanks for your help!! –  Mike Davies Apr 27 '12 at 21:59

$g^{m} \equiv 1 \mod p$ if and only if $\mathrm{ord}_p(g)$ divides $m$.

Since $g$ is primitive root, we get that $p-1=\mathrm{ord}_p(g)$ has to divide $5n$.

Can you finish the problem now?

-