[Moderator edit: This post refers to an older version of post #1. It is now obsolete.] sam-n wrote: show that If p-1 isn't empty of perfect square( I mean that we can show p-1 =k ²m) Use "square free" for "empty of perfect square", or "not square free" to deny it.

Let q be a prime s.t. q² | p-1. Now let x be a residue (mod p) which has order q (this means that x^q=1(p) and q is the smallest with this property). Now assume a is a primitive root but xa isn't. Then there exists t|p-1 s.t. xa has order t (t<p-1). From here we get (xa)^t=1(p)=>(xa)^qt=1(p)=>a^qt=1(t), but a^p-1=1(p) so a^(qt,p-1)=1(p). a is a primitive root of p, so (qt,p-1)=p-1, so p-1 | qt. From the fact that t<p-1 it's easy to get qt=p-1, so t=(p-1)/q, which is divisible with q, so (x^-1)^t=1(p) and from the fact that (xa)^t=1(p) we get a^t=1(p), which is false because a is a primitive root. This shows that a=primitive root=>xa also primitive root, so all of the numbers a, xa, x²a, ..., x^q-1a are primitive roots of p, but it's easy to check that their sum is 0(p), so the set of primitive roots of p can be partitioned in such sets of q elements each, each set having the sum of its elements 0(p), so the entire sum is 0(p). I think that in all cases S=u(p-1)(p), where u is Mobius' function. This means that S=0(p) when p-1 isn't square-free (I've just showed that), S=1(p) when p-1 is square-free and has an even number of prime divisors and S=-1(p) when p-1 is square-free and has an odd number of prime divisors. I don't have the proof for the last 2 statements, but it loks that way (I checked some numbers on my computer). I might, of course, be wrong. [Moderator edit: I don't understand why "it's easy to get qt=p-1", but fortunately, all that is used later is the assertion that $t$ is divisible by $q$, and this assertion is obvious anyway (since $q^2 \mid p-1 \mid qt$). -- Darij]

We can use cyclotomic polynomials. The primitive roots modulo p are the roots of the polinomial phi_p-1(x) in the field Z_p(the p-1'th cyclotomic polynomial). I think that from here we can derive that their sum is u(p-1) (as I have already mentioned, u is Mobius' function). In order to do this we must show that the second coefficient of phi_n is -u(n). I think this shouldn't be too hard, right? This would solve everything in just one step.

excuse me grobber ,I did'n understood what does cyclotomic polynomials& phip-1(x) mean?

The n'th cyclotomic polynomial, phi_n(x)= \pi{t is a primitive root of 1 of order n}(x-t), or, in other words, \pi{(k,n)=1}(x-(cos(2k\pi)+isin(2k\pi))).

I found this problem in Hojoo Lee's book on number theory (a colection of problems): Show that the sum of all the primitive roots mod p is congruent to u(p-1) (mod p). It doesn't say that p is a prime, but I assume that's the case. This means that what I was saying a few posts ago is true (" I think that in all cases S=u(p-1)(mod p)"). The reference in Hojoo Lee's file for this problem is Km, problems sheet 1-3. Km means Keith Matthews, and you can find something here: http://www.numbertheory.org/courses/MP313/index.html It might be helpful. In order to show that S=u(p-1) (mod p) it's enough to use the fact that the primitive roots of p are the roots in Z_p of the polynomial phi_p-1(x)=0 (phi_p-1 is, as before, the p-1'th cyclotomic polynomial), and then use the fact that phi_n(x)= \pi{d|n}(x^d-1)^u(n/d). Try it, this part isn't hard. What isn't exactly clear to me is why the primitive roots are the roots of that polynomial in Z_p. This is true for the primitive roots of 1 of order p-1, but what does it have to do with the divisibility with p? It's a bit unclear to me, but I still used it .