6
$\begingroup$

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.

  • 2
    What Geoff says. And remember that $\phi(n)$ is even more often than not.2012-07-12

3 Answers 3

4

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
    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.2012-11-06
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$

  • 0
    $\,\frac{1}{3}=3^{-1}=5\pmod 7\,$ , since $\,3\cdot 5=1\pmod 7\,$2012-07-12
2

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.