# Sum of primitive roots is congruent to $\mu(p-1)$ using Moebius inversion?

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?

-
 possible duplicate of Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$ – TMM Jan 1 at 13:07

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