# 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 $\displaystyle \phi(p-1)$ primitive roots of p is congurent modulo p to$\displaystyle (-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 $\displaystyle a_1,a_2,...,a_{\phi(p-1)}$ be the primitive roots of $\displaystyle p$. Let $\displaystyle a_1 = r$ then $\displaystyle a_2 \equiv r^{b_2}$ where $\displaystyle 1< b_2 < p-1$ and $\displaystyle \gcd( b_2, p-1)=1$. Similarly $\displaystyle a_3 \equiv r^{b_3}$ and so one.
Thus, $\displaystyle r^{1},r^{b_2},...,r^{b_{\phi(p-1)}}$ are all the primitive roots. Now one of the exponents of $\displaystyle r$ are the same, and they are all relatively prime to $\displaystyle p-1$. By pigeonholing we see that they are a premutation of all integers relatively prime to $\displaystyle p-1$ and less than it.
Thus, $\displaystyle 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 $\displaystyle c_1+...+c_{\phi(p-1)}$ where $\displaystyle c_1,c_2,...,c_{\phi(p-1)}$ are all the positive integers less than $\displaystyle p-1$ and are congruent to $\displaystyle p-1$ written in increasing order. Note that $\displaystyle 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 $\displaystyle p-1$, thus, $\displaystyle c_1+...+c_{\phi(p-1)} = [c_1 - (p-1)]+...+[c_{\phi(p-1)} - (p-1)]$, thus, $\displaystyle c_1+...+c_{\phi(p-1)} = (1/2)(p-1)\phi(p-1)$.
Thus, we have,
$\displaystyle 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 $\displaystyle r^{(p-1)/2} \equiv -1 (\bmod p)$ (remember that?).
Thus, $\displaystyle r^{c_1+...+c_{\phi(p-1)}} \equiv (-1)^{\phi(p-1)} (\bmod p)$.
• Jan 14th 2008, 07:14 PM
midosoft
really thnx man