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}$.
 A: 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$.
A: 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$.  
A: Let $f(d)$ sum the elements $u$ of order $d$, and let $g(d)$ sum the elements $u$ whose $d$th 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.)
A: The appearance of the Möbius function is a hint that Möbius inversion is involved.
To get it out of the way, the special case $p=2$ is trivial as $1$ is the only primitive root and equals $\mu(2-1)$.
Now, assume $p$ is an odd prime, for which there must a primitive root $g$.
Like the other answers, define $f(n)$ as the sum of elements or order $n$ (in the multiplicative group mod $p$). Since primitive roots have order $p-1$, our answer is $f(p-1)$.
As an aside, the elements of order $n$ are exactly the $g^k$ where $(p-1)/\gcd(k, p-1) = n$, so for $n \mid p-1$,
$$
f(n) = \sum_{\gcd(k,p-1) = (p-1)/n} g^k
$$
Also by Lagrange's theorem, $f(n) = 0$ if $n \nmid p-1$.
Now define the summatory function $F(n) = \sum_{d \mid n} f(d)$, the sum of the elements of order dividing $n$. By the Möbius inversion formula,
$$
f(p-1) = \sum_{d \mid p-1} \mu(d) F\left(\frac{p-1}{d} \right)
$$
For all $d \mid p-1$, the elements with order dividing $(p-1)/d$ are powers of $g^d$, as $g^x$ has order $(p-1)/\gcd(p-1, x)$ which divides $(p-1)/d$ iff $d \mid \gcd(p-1,x)$, satisfied iff $x = kd$ for $1 \le k \le (p-1)/d$.
Then for $d= p-1$, $F((p-1)/d) = 1$, and for $d < p-1$,
$$
F\left(\frac{p-1}{d} \right) = \sum_{k=1}^{(p-1)/d} g^{kd} = g^d \left(\frac{g^{p-1}-1}{g^d-1} \right) \equiv 0 \mod p
$$
The geometric series term is valid since $d < p-1$ so $g^d -1 \not \equiv 0 \mod p$, while $g^{p-1} - 1 \equiv 0 \mod p$.
We conclude $f(p-1) \equiv \mu(p-1) \mod p$.
