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.

If $p$ is a prime, show that the product of the $\phi(p-1)$ primitive roots of $p$ is congruent modulo $p$ to $(-1)^{\phi(p-1)}$.

I know that if $a^k$ is a primitive root of $p$ if gcd$(k,p-1)=1$.And sum of all those $k's$ is $\frac{1}{2}p\phi(p-1)$,but then I don't know how use these $2$ facts to show the desired result.
Please help.

share|improve this question
3  
Hint: If $a$ is a primitive root, so is $a^{-1}.$ –  Geoff Robinson Jul 12 '12 at 13:09
    
Use $a^p=a \mod p$. –  i. m. soloveichik Jul 12 '12 at 13:11
2  
What Geoff says. And remember that $\phi(n)$ is even more often than not. –  Jyrki Lahtonen Jul 12 '12 at 13:19
add comment

3 Answers 3

We know $ ord_m(a^k) =\frac{d}{(d, k)} $ where d=$ord_ma$ => $ord_pa=ord_p(a^{-1})$

There are $\phi(p-1)$ primitive roots for prime $p$.

As $\phi(n)$ is even for $n>2$ ,i.e. for $p-1>2$.

So,for $p>3$, we can always find $a^{-1}$ for each primitive root $a$ of $p$.

Now if $a≡a^{-1}(mod\ p)$ =>$a^2≡1(mod\ p)$ =>$ord_pa|2$.

But $\phi(p-1)$>2 for n>6.

So, there will be $\frac{\phi(p-1)}{2}$ pairs each having product $≡1(mod\ p)$ if $p>3$. The product is ≡$(-1)^{\phi(p-1)}\pmod p$ , for $p>3$ .

For $p=3$, the only primitive root is $=2 ≡-1(mod 3)=(-1)^{(\phi(3)-1)}\,$ , as $\,\phi(3)=2$

share|improve this answer
1  
One small detail: if $a$ is a primitive root then $a^{-1}\ne a$ unless $p=3$. –  lhf Jul 12 '12 at 13:32
    
I didn't understand this $\text{ord}_pa=\text{ord}_pa^{-1}\\$. e.g. how $\text{ord}_73=\text{ord}_7\frac{1}{3}$? means $\frac{1}{3}$ is bothering me. –  Saurabh Jul 12 '12 at 13:43
    
$\,\frac{1}{3}=3^{-1}=5\pmod 7\,$ , since $\,3\cdot 5=1\pmod 7\,$ –  DonAntonio Jul 12 '12 at 14:43
add comment

We know $ ord_m(a^k) =\frac{d}{(d, k)} $ where d=$ord_ma$ => $ord_ma=ord_m(a^{-1})$ where m is a natural number.

So, $a,a^{-1}$ must belong to the same order(d).

Now by the previous solution, $a≢a^{-1}(mod\ m)$ if d>2.

So, the product of all number belonging to the same order(d)≡1(mod m) if d>2.

Now, $\phi(m)>2$ if m=5 or >6.

Now, $\phi(m)=2$ if m=3,4,6.

In all the three cases, the primitive root is (m-1)≡-1(mod m).

Here m does not need to be prime and $2<d≤\phi(m)$.

share|improve this answer
add comment

If $a^k$ is a primitive root modulo $p$, then so is $a^{-k}$. Thus, if $p-1$ is even, then the sum of coprime integers between 1 and $p-1$ with $p-1$ must be =$\phi(p-1)(p-1)/2$, and hence the product of $\phi(p-1)$ primitive roots modulo p must be $a^{\phi(p-1)(p-1/2)}\equiv(-1)^{\phi(p-1)} \pmod p$. If $p-1$ is odd, then the result is trivial, as $p=2$.

share|improve this answer
    
Notice that, since $a$ is a primitive root modulo $p$, $a^{(p-1)/2}$ must be congruent to a square root of 1, but at the same time different from 1, modulo $p$. So the only possibility that occurs is -1. –  awllower Nov 6 '12 at 17:37
add comment

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.