Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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