problem in primitive roots

• Dec 18th 2007, 01:13 PM
midosoft
problem in primitive roots
i wish any one can hepl me with this problems

1) if p is prime , show that th product of the $\phi(p-1)$ primitive roots of p is congurent modulo p to $(-1)^\phi(p-1)$.

[hint: if r is primitive root of p , then r^k is primitive root of p provided that gcd(k,p-1)= 1 ]

**********

2) use the fact that each prime p has a primitive root to give a different proof of Wislon's theroem.
[hint : if p has a primitive root r, then (p-1)!=r^1+2+..+(p-1)(modp)]
• Dec 18th 2007, 01:29 PM
ThePerfectHacker
Post #5 might help. Assume that p>2.

Let $a_1,a_2,...,a_{\phi(p-1)}$ be the primitive roots of $p$. Let $a_1 = r$ then $a_2 \equiv r^{b_2}$ where $1< b_2 < p-1$ and $\gcd( b_2, p-1)=1$. Similarly $a_3 \equiv r^{b_3}$ and so one.
Thus, $r^{1},r^{b_2},...,r^{b_{\phi(p-1)}}$ are all the primitive roots. Now one of the exponents of $r$ are the same, and they are all relatively prime to $p-1$. By pigeonholing we see that they are a premutation of all integers relatively prime to $p-1$ and less than it.
Thus, $r^1 \cdot r^{b_2} \cdot ... \cdot r^{ b_{\phi(p-1)}} \equiv r^{c_1+...+c_{\phi(p-1)}} (\bmod p)$.
The question now is what is a nice formula for $c_1+...+c_{\phi(p-1)}$ where $c_1,c_2,...,c_{\phi(p-1)}$ are all the positive integers less than $p-1$ and are congruent to $p-1$ written in increasing order. Note that $c_1 - (p-1),c_2-(p-1),...,c_{\phi(p-1)} - (p-1)$ all again a permutation of all the relatively prime integers to $p-1$, thus, $c_1+...+c_{\phi(p-1)} = [c_1 - (p-1)]+...+[c_{\phi(p-1)} - (p-1)]$, thus, $c_1+...+c_{\phi(p-1)} = (1/2)(p-1)\phi(p-1)$.
Thus, we have,
$r^{c_1+...+c_{\phi(p-1)}} \equiv r^{(1/2)(p-1)\phi(p-1)} \equiv\left( r^{(p-1)/2} \right)^{\phi(p-1)} (\bmod p)$.
But $r^{(p-1)/2} \equiv -1 (\bmod p)$ (remember that?).
Thus, $r^{c_1+...+c_{\phi(p-1)}} \equiv (-1)^{\phi(p-1)} (\bmod p)$.
• Jan 14th 2008, 07:14 PM
midosoft
really thnx man