a formula involving order of Dirichlet characters, $\mu(n)$ and $\varphi(n)$

Solution 1:

Fix $n$ and define

$$f(d)=\sum_{o(\chi)=d}\chi(n).$$

Let's show $f$ is multiplicative. First off, let $g$ be a generator for $(\mathbb{Z}/p\mathbb{Z})^\times$ and write $n=g^k$, then let $\psi$ be a generator for the group $\{\chi:\chi^d=1\}$, in which case we may say $o(\chi)=d\iff \chi=\psi^e$ for a unit $e$ mod $d$. As $\psi(g)$ is a primitive $d$th root of unity, the values $\psi(g)^e$ (as $e$ ranges over units mod $d$) will be all primitive $d$th roots of unity, i.e. all $\zeta$ with $o(\zeta)=d$. Thus

$$ f(d)=\sum_{(m,d)=1} \psi^m(g^k)=\sum_{o(\zeta)=d}\zeta^k. $$

This is known as a Ramanujan sum. We want to see that $f(d_1d_2)=f(d_1)f(d_2)$ whenever $d_1,d_2$ are coprime. (Technically since $k$ is an integer mod $p-1$ the formula only makes sense for when $d\mid(p-1)$, however if we interpret it as a function of a usual integer $k$ we can talk about any $d$ values we want and it will in fact be multiplicative).

The key is the Chinese Remainder Theorem $(\mathbb{Z}/d_1d_2\mathbb{Z})^\times\cong(\mathbb{Z}/d_1\mathbb{Z})^\times\times(\mathbb{Z}/d_2\mathbb{Z})^\times$ which for our purposes means every $d_1d_2$th root of unity is uniquely expressible as a product of $d_1$th and $d_2$th roots of unity, and in particular primitive $d_1d_2$th roots of unity are uniquely expressible as products of primitive $d_1$th and $d_2$th roots of unity. Therefore,

$$ \begin{array}{ll} f(d_1)f(d_2) & \displaystyle =\left(\sum_{o(\zeta)=d_1}\zeta^k\right)\left(\sum_{o(\xi)=d_2}\xi^k\right) \\[7pt] & \displaystyle =\sum_{\substack{o(\zeta)=d_1 \\ o(\xi)=d_2}} (\zeta\xi)^k =\sum_{o(\eta)=d_1d_2}\eta^k \\[7pt] & =f(d_1d_2). \end{array} $$

Now, if $g(m)$ is any multiplicative function then we may write $g(m)=\prod_{q^r\| m}g(q^r)$, where $q^r\|m$ means $q^r$ is the power of a prime $q$ that appears in $m$'s prime factorization. Moreoever, if $g(m)$ is multiplicative then so is $\sum_{d\mid m}g(d)$ as a function of $m$, in which case it also gets a factorization that looks like $\prod_{q^r\|m} \sum_{d\mid q^r}g(d)$. If $g(d)$ has a $\mu(d)$ factor, then $\sum_{d\mid q^r}g(d)=g(1)+g(q)$ because $g(q^r)=0$ if $r>1$. Therefore we have

$$ \sum_{d\mid(p-1)}\frac{\mu(d)}{\varphi(d)}f(d)=\prod_{q\mid (p-1)}\left(1-\frac{1}{\varphi(q)}f(q)\right) $$

as desired.

Solution 2:

For $n \equiv 0 \bmod p$ it is not correct, since it is $0 = 1$. Let $gcd(n,p) = 1$ :

$\chi$ is a character modulo $p$. Let $g$ be a generator of $\mathbb{F}_p^{\times}$, and $f(n)$ the discrete logarithm such that $n \equiv g^{f(n)} \bmod p$, with $f$ being a bijection $ \{1\ldots p-1\} \to \{1\ldots p-1\}$.

Then the characters modulo $p$ all are of the form $$\chi(n) = e^{2 i \pi a f(n) / (p-1)}$$

Hence $o(\chi) = d$ iff $d\frac{a }{p-1}$ is an integer i.e. $\frac{p-1}{d} | a$.

So that $$\sum_{o(\chi) = d} \chi(n) = \sum_{m = 1}^{d} e^{2 i \pi m f(n) / d} = d 1_{d | f(n)}$$ and $$\sum\limits_{d|p - 1} {\frac{{\mu (d)}}{{\varphi (d)}}} \sum\limits_{o(\chi ) =d }\chi(n) = \sum_{d | p-1} \mu(d) \frac{d}{\varphi(d)} 1_{d | f(n)} = \sum_{d | gcd(p-1,f(n))} \mu(d) \frac{d}{\varphi(d)}$$

while $$\prod\limits_{j = 1}^r {(1 - \frac{1}{{\varphi ({q_j})}}} \sum\limits_{o(\chi ) = {q_{_j}}} {\chi (n)} ) = \prod_j (1- \frac{q_j}{q_j-1} 1_{q_j | f(n)}) = \prod_{q |gcd(p-1,f(n))} \frac{(-1)}{q-1}$$

The conclusion is that $g(n) = \mu(n)\frac{n}{\varphi(n)}$ is multiplicative so that $$\sum_{n=1}^\infty g(n) n^{-s} = \prod_p 1 + \sum_{k=1}^\infty g(p^k) p^{-sk} = \prod_p 1 - \frac{p}{p-1}p^{-s}$$ and $$\sum_{n=1}^\infty \sum_{d | n} g(d) n^{-s} = \prod_p \frac{1 - \frac{p}{p-1}p^{-s}}{1-p^{-s}} = \prod_p 1+\sum_{k=1}^\infty \left(1-\frac{p}{p-1}\right)p^{-sk} = \prod_p 1-\sum_{k=1}^\infty \frac{p^{-sk}}{p-1}$$ whence, for any $N$, in particular for $N = gcd(p-1,f(n))$ : $$\sum_{d | N}\mu(d)\frac{d}{\varphi(d)} = \sum_{d | N} g(d) = \prod_{p | N} \frac{(-1)}{p-1}$$

$$\displaystyle\sum\limits_{d|p - 1} {\frac{{\mu (d)}}{{\varphi (d)}}} \sum\limits_{o(\chi ) =d }\chi(n) = \sum_{d | gcd(p-1,f(n))} \mu(d) \frac{d}{\varphi(d)} $$ $$= \prod_{q |gcd(p-1,f(n))} \frac{(-1)}{q-1} = \prod\limits_{j = 1}^r {(1 - \frac{1}{{\varphi ({q_j})}}} \sum\limits_{o(\chi ) = {q_{_j}}} {\chi (n)} )$$