Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
What Geoff says. And remember that $\phi(n)$ is even more often than not. – Jyrki Lahtonen Jul 12 '12 at 13:19

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

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|cite|improve this answer
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

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|cite|improve this answer

Your Answer


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.