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

Question

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

Answer 1

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$.

Answer 2

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$.

Answer 3

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.)

Answer 4

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$.