# Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$

Suppose that $p$ is a prime. Prove that the sum of the primitive roots modulo $p$ is congruent to $\mu(p − 1) \pmod{p}$.

-
Please don't post questions in the imperative mode; this may be homework for you, but you aren't assigning it as homework to us. You are asking a question, so kindly phrase it like a question. Also, given that this is homework, it would be nice (and polite, and helpful) if you say what you have tried, and where you are stuck. That way the answers can deal directly with whatever it is you are having trouble with. – Arturo Magidin Mar 7 '11 at 5:40
Hint: If $latex f = x^n + f_{n-1} x^{n-1} + \cdots + f_0$ is a polynomial whose roots are $r_1$, ..., $r_n$, then $- \sum r_i = f_{n-1}$. – David Speyer Mar 7 '11 at 16:31
I've seen this result in a few books. But I can't see why it is interesting. Can someone please enlighten me? – lhf Jan 12 '12 at 13:13
– barto Mar 14 '15 at 11:37

If $g$ is a primitive root of $p$ then Thm 10.9 of Apostol says the sum in question, $S$, is given by

$$S=\!\!\!\!\!\sum_{\substack{k=1\\(k,p-1)=1}}^{p-1}\!\!\!\!\!\!g^k=\sum_{k=1}^{p-1}g^k\sum_{\substack{d|k\\d|p-1}}\mu(d)=\sum_{d|p-1}\mu(d)\sum_{r=1}^{(p-1)/d}\!\!g^{rd}$$

The inner sum is congruent to $0$ unless $d=p-1$ when it is congruent to $1$.

-
For more than one condition under the $\sum$ sign, you can use \sum_{\substack{xx\\ yy}}. – barto Mar 14 '15 at 11:31

If $p - 1 = a^\alpha b^\beta c^\gamma ...$. Then if $A$ is an element of order $a^\alpha$, $B$ is an element of order $b^\beta$, etc. then ABC... is a primitive root.

If A, A', A'', etc. are the elements of order $a^\alpha$, B, B', B'', etc. are the elements of order $b^\beta$, then

(A + A' + ...) (B + B' + ...) (C + C' + ...) ... is the sum of the primitive roots.

Now consider the sum of the terms in any one of the factors, keeping in mind the fact that if $k$ is the order of $y$ and $l$ is relatively prime to $k$, then $y^l$ also has order $k$.

-
I am glad to see this answer here; it reminds me of some forgotten facts... May I ask you a question? Is this answer out of the book Disquisitions Arithmeticae by Gauß? I see some hints and footprints here. Thanks for sharing. – awllower Feb 8 '12 at 9:12

Let f(d) sum the elements u of order d, and let g(d) sum the elements u whose dth powers are 1. Thus g can be evaluated as a geometric sum, and also it has an expression in terms of f that sets up Möbius inversion to give f in terms of g; the exercise is requesting f(p − 1), so we are done. (This answer essentially repeats the others, but maybe invoking the Möbius inversion rather than redoing it in the middle of other things is tidy.)

-