Wikipedia has the result that Gauss proved that for a prime number $p$ the sum of its primitive roots is congruent to $\mu(p − 1) \pmod{p}$ in Article 81.
I read it, but is there a faster proof using Moebius inversion instead of case by case checking?
I tried the following:
Let $f(d)$ be the sum of all the $d$th roots of unity. Then I think we have $$ \sum_{d\mid p-1}f(d)\equiv \sum_{x\in\mathbb{Z}_p^\times}x\equiv 0\pmod{p} $$ since every element of $\mathbb{Z}_p^\times$ is a $d$th root of unity for some $d\mid p-1$.
So I define $F(n)=\sum_{d\mid n}f(d)$. By Moebius inversion, $$ f(n)=\sum_{d\mid n}\mu(d)F(n/d). $$ The sum in question is the case where $n=p-1$, so $$ f(p-1)=\sum_{d\mid p-1}\mu(p-1)F((p-1)/d) $$ and I want to show this is congruent to $\mu(p-1)\pmod{p}$. Since $f(1)=1$, $F(1)=1$, so I'm just trying to show $F((p-1)/d)\equiv 0$ when $(p-1)/d\neq 1$ and I believe the result would follow. Does anyone know how to show that if it is true, or fix the argument otherwise?
First note that if $$ F(n)=\sum_{(k,n)=1}^{1\leq k\leq n}f\left(\frac{k}{n}\right), $$ then $$ \sum_{d\mid n}F(d)=\sum_{k=1}^n f\left(\frac{k}{n}\right). $$
For consider $f\left(\frac{k}{n}\right)$ with $1\leq k\leq n$. Then $$ \frac{k}{n}=\frac{k/(k,n)}{n/(k,n)}=\frac{k^\prime}{n^\prime} $$ where $k^\prime=k/(k,n)$ and $n^\prime=n/(k,n)$ are coprime, and $n^\prime\mid n$. Hence this terms corresponds to a term in $F(n^\prime)$. Conversely, a term on the right hand side has form $f\left(\frac{k}{d}\right)$ for $d\mid n$ and $1\leq k\leq d$ with $(k,d)=1$. If $dj=n$, then we have $f\left(\frac{k}{d}\right)=f\left(\frac{kj}{n}\right)$, and $1\leq kj\leq n$.
So if $g$ is a primitive root, the sum in question is congruent to $$ S=\sum_{(k,p-1)=1}^{1\leq k\leq p-1} g^k $$ as we want to sum over all powers of $g$ with exponent coprime to $\phi(p)=p-1$. So let $$ S_n=\sum_{(k,n)=1}^{1\leq k\leq n} a^{k/n}. $$ By the above observation, $$ \sum_{d\mid n}S_d=\sum_{k=1}^n a^{k/n}=\frac{a^{1/n}-a^{(n+1)/n}}{1-a^{1/n}}. $$ Using Möbius inversion, $$ S_n=\sum_{d\mid n}\frac{a^{1/d}-a^{(d+1)/d}}{1-a^{1/d}}\cdot\mu\left(\frac{n}{d}\right). $$
In particular, setting $n=p-1$ and $a=g^{p-1}$ yields $$ S=\sum_{d\mid p-1}g^{(p-1)/d}\left(\frac{1-g^{p-1}}{1-g^{(p-1)/d}}\right)\cdot\mu\left(\frac{p-1}{d}\right). $$
But $p\mid 1-g^{p-1}$, and $p\nmid 1-g^{(p-1)/d}$ when $d\neq 1$ is a proper divisor since $g$ is a primitive root. So all terms with $d\neq 1$ vanish modulo $p$, and when $d=1$, $$ S\equiv g^{p-1}\mu(p-1)\equiv\mu(p-1)\pmod{p}. $$