Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
possible duplicate of Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$ – TMM Jan 1 '13 at 13:07
The congruence $\sum_{d\mid p-1}f(d)\equiv \sum_{x\in\mathbb{Z}_p^\times}x\equiv 0\pmod{p}$ doesn't make sense: The left and middle sides are in $\mathbb{Z}_p$, while the $\equiv$ signs suggest that you are working in $\mathbb{Z}$. – darij grinberg Sep 12 '15 at 16:48
up vote 8 down vote accepted

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

share|cite|improve this answer
Your posts on number theory are really illuminating, Ben. Thanks. – Pedro Tamaroff Oct 13 '13 at 19:34
@PedroTamaroff Thanks for the kind words, Peter/(Pedro?)! – Ben West Oct 14 '13 at 2:28
There is some confusing notation here, to say the least. I assume your $f$ is supposed to be a map from $\dfrac{1}{p-1}\mathbb{Z}$ to $\mathbb{Q}$, and that $a^x$ is shorthand for $g^{\left(p-1\right)x}$ whenever $x \in \dfrac{1}{p-1}\mathbb{Z}$ ? – darij grinberg Sep 12 '15 at 16:47

Here is a straightforward solution involving sums of roots of cyclotomic polynomials.

We work in some field $K$.

We show that the sum of the primitive $n$th roots of unity is $\mu(n)$. Here, we define the primitive $n$th roots of unity to be the roots of the cyclotomic polynomial $\Phi_n(x)$ in some fixed algebraic closure of $K$, counted with multiplicities. (This is important for the case of finite $K$; there, the notation is non-standard. Of course, when $K = \mathbb{F}_p$ and $n = p-1$, then the primitive $n$th roots of unity are precisely the primitive roots of $\mathbb{F}_p$, and all multiplicities are $1$.)

We proceed using strong induction. Let $S_n$ denote the sum of the primitive $n$th roots of unity. Our base case is: $\Phi_1(x)=x-1$, by Vieta's formulas so $S_1=1=\mu(1)$. Now, suppose the proposition holds for all $1\le n\le k-1$. We have $$x^k-1=\prod_{d|k}\Phi_d(x)=\prod_{d|k}(x^d-S_d x^{d-1}+\ldots) = x^k-cx^{k-1}+\ldots, $$ where $c=\displaystyle\sum_{d|k}S_d$. However, since $k\ge 2$, we have $\displaystyle\sum_{d|k}S_d=0$, which means $$S_k+\sum_{\substack{d|k;\\ d<k}}\mu(d)=S_k + \left(\sum_{d|k}\mu(d)\right)-\mu(k) = 0.$$ It follows that $S_k=\mu(k)$, since $\sum_{d|k}\mu(d)=0$. Thus the induction is complete.

It follows as a corollary that if $g_1, g_2,\ldots, g_{\varphi(p-1)}$ are the primitive roots mod $p$, then $$\sum_{i=1}^{\varphi(p-1)}g_i\equiv\mu(p-1)\pmod{p}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.