# Show that the product of the $\phi(p-1)$ primitive roots of $p$ is congruent modulo $p$ to $(-1)^{\phi(p-1)}$

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.

• 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$.

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

• 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)$.