Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

up vote 5 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|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
add comment

Here is a particularly nice solution involving sums of roots of cyclotomic polynomials.

We show that the sum of the primitive $n$th roots of unity is $\mu(n)$.

We proceed using strong induction. Let $S_n$ denote the sum of the primitive nth 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_{\stackrel{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|n}\mu(d)=0$. Thus the induction is complete.

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

share|improve this answer
add comment

Your Answer

 
discard

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.