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.

  • 3
    $\begingroup$ Hint: If $a$ is a primitive root, so is $a^{-1}.$ $\endgroup$ – Geoff Robinson Jul 12 '12 at 13:09
  • $\begingroup$ Use $a^p=a \mod p$. $\endgroup$ – i. m. soloveichik Jul 12 '12 at 13:11
  • 2
    $\begingroup$ What Geoff says. And remember that $\phi(n)$ is even more often than not. $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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$

  • 2
    $\begingroup$ One small detail: if $a$ is a primitive root then $a^{-1}\ne a$ unless $p=3$. $\endgroup$ – lhf Jul 12 '12 at 13:32
  • $\begingroup$ 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. $\endgroup$ – Saurabh Jul 12 '12 at 13:43
  • $\begingroup$ $\,\frac{1}{3}=3^{-1}=5\pmod 7\,$ , since $\,3\cdot 5=1\pmod 7\,$ $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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