2
$\begingroup$

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.

2 Answers 2

2

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.

  • 0
    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 n2012-04-27
  • 0
    @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}$?2012-04-27
  • 0
    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!2012-04-27
  • 0
    @MikeDavis: Sorry; I misunderstood your comment... Yes, you have that many solutions. The one who was slow there was me.2012-04-27
  • 0
    No bother, thanks for your help!!2012-04-27
2

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