Let $p$ a prime number, ${q_{_1}}$,..., ${q_{_r}}$ are the distinct primes dividing $p-1$, ${\mu}$ is the Möbius function, ${\varphi}$ is Euler's phi function, ${\chi}$ is Dirichlet character $\bmod{p}$ and ${o(\chi)}$ is the order of ${\chi}$.

How can I show that: $$\sum\limits_{d|p - 1} {\frac{{\mu (d)}}{{\varphi (d)}}} \sum\limits_{o(\chi ) = d} {\chi (n)} = \prod\limits_{j = 1}^r {(1 - \frac{1}{{\varphi ({q_j})}}} \sum\limits_{o(\chi ) = {q_{_j}}} {\chi (n)} ) \quad ?$$


Fix $n$ and define


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.


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

  • $\begingroup$ @user1952009 what you mean ${1_{d|f(n)}}$? $\endgroup$ – euclid Jan 7 '17 at 4:30
  • $\begingroup$ @euclid Often people use $1_X$ as an indicator function, in this case taking the value $1$ when $d$ divides $f(n)$ and taking the value $0$ otherwise. $\endgroup$ – arctic tern Jan 8 '17 at 5:29
  • $\begingroup$ user1952009, in your equality, $$\sum_{o(\chi)=d}\chi(n)=\sum_{m=1}^d e^{2\pi i mf(n)/d},$$ the left sum has at most $\varphi(d)$ summands but the right sum has $d$ summands. You seem to be summing over all $\chi$ with $\chi^d=1$ instead of all $\chi$ with $o(\chi)=d$ (although ironically, the sum is still a multiplicative function of $d$ either way, hence the rest of your proof would have worked if it was $\chi^d=1$ below the summations instead of $o(\chi)=d$). $\endgroup$ – arctic tern Jan 8 '17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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