Arithmetic Functions Summation

Question

Ok so this was one of the problems in my book, and it goes:

Show that for each positive integer $n$:$$\sum_{a=1,(a,n)=1}^n e^{\frac{2\pi a i}{n}} = \mu(n)$$.

$Proof$ : Let $\Phi(n) = \sum_{a=1,(a,n)=1}^n e^{\frac{2\pi a i}{n}} $, we firstly like to prove that $\Phi(n)$ is multiplicative. To do this we denote $\mathbb{R} (n)$ as the complete residue system modulo $n$. We make a claim that given some $c \in \mathbb {R}(m_1m_2)$, with $(m_1,m_2)=1$, there exists a unique $a \in \mathbb{R}(m_1)$ and $b \in \mathbb{R}(m_2)$ such that $c = am_2+bm_1 \bmod(m_1m_2)$. We see by the Chinese Remainder Theorem that $|\mathbb{R}(m_1m_2)|=|\mathbb{R}(m_1)||\mathbb{R}(m_2)|$. Clearly $am_2+bm_1$, $a \in \mathbb{R}(m_1)$, $b \in \mathbb{R}(m_2)$ consists of $|\mathbb{R}(m_1m_2)|=|\mathbb{R}(m_1)||\mathbb{R}(m_2)|$ combinations exactly. Additionally we have $(am_2+bm_1, m_1)=(am_2,m_1)=1$ and $(m_2,m_1)=1$ and $(am_2+bm_1, m_2)=1$ similarly, so that $am_2+bm_1 \in \mathbb{R}(m_1m_2)$. So it suffices we prove its uniqueness:

If we let $a_1m_2+b_1m_1\equiv a_2m_2+b_2m_1, a_i\in\mathbb{R}(m_1), b_i \in \mathbb{R}(m_2)$ for $i=1,2$. Then we get, $(a_1-a_2)m_2\equiv (b_2-b_1)m_1 \bmod (m_1m_2)$. Thus $m_1|(a_1-a_2)m_2$ however we know that $(m_1,m_2)=1$ which implies $m_1|(a_1-a_2)$. Using this result we can deduce that: $a_1 \equiv a_2 \bmod m_1$ and $b_1 \equiv b_2 \bmod m_2$. Hence, $cm_1+bm_2 \le b \le m_1, (b,m_1)=1, 1\le c\le m_2, (c,m_2)=1$ gives a complete reduced residue system modulo $m_1m_2$. Now that we established the above, we can write: $$\Phi(m_1m_2)=\sum_{a=1,(a,m_1m_2)=1}^{m_1m_2} e^{\frac{2\pi ia}{m_1m_2}}$$ $$=\sum_{a=1,(a,m_1m_2)=1}^{m_1m_2} e^{\frac{2\pi i a}{m_1m_2}}$$ $$=\sum_{b=1,(b,m_1)=1}^{m_1} \sum_{c=1,(c,m_2)=1}^{m_2}e^{\frac{2\pi i(cm_1+bm_2)}{m_1m_2}}$$ $$=\sum_{b=1,(b,m_1)=1}^{m_1} e^{\frac{2\pi ib}{m_1}}\sum_{c=1,(c,m_2)=1}^{m_2}e^{\frac{2\pi ic}{m_2}}$$ $$=\Phi(m_1)\Phi(m_2)$$ Hence we proved the multiplicativity of $\Phi(n)$.

Then the next step of the proof, we let $n = p^r$, and consider when $r=0$ and $r=1$ and $r \ge 2$. (Note we need to consider $n = 1$ separately as no prime divides 1).

Case $r=0$: We have, $\Phi(1)=e^{2\pi i}=1=\mu(1)$. Also when $n \ge 2$, we know that $e^{\frac{2\pi i}{n}}$ is an $n$-th root of unity which is not $1$, so we have: $$\sum_{a=0}^{n-1} e^{\frac{2\pi ia}{n}}=\frac{e^{\frac{2\pi in}{n}}-1}{e^{\frac{2\pi i}{n}}-1}=0$$ or $$\sum_{a=0}^{n-1} e^{\frac{2\pi ia}{n}}=-1$$

Thus when r = 1, we have $\sum_{a=1,(a,p)=1}^p e^{\frac{2\pi a i}{p}}=\sum_{a=0}^{p-1} e^{\frac{2\pi ia}{p}}=-1=\mu(p)$.

Case $r\ge 2$, the set consisting of ${{1 \le a \le p^r: (a,p^r)=1}}$ is equivalent to the set ${j+kp: 1 \le j \le p-1, 0\le k\le p^{r-1}-1}$. Hence we have:

$$\Phi(p^r)=\sum_{a=1,(a,p^r)=1}^{p^r} e^{\frac{2\pi a i}{p^r}}$$ $$=\sum_{j=1}^{p-1}\sum_{k=0}^{p^r-1} e^{\frac{2\pi i (j+kp)}{p^r}}$$ $$=\sum_{j=1}^{p-1}e^{\frac{2\pi i j}{p^r}}\sum_{k=0}^{p^r-1} e^{\frac{2\pi i kp}{p^r}}$$ $$=\sum_{j=1}^{p-1}e^{\frac{2\pi i j}{p^r}}\times 0$$ $$0=\mu(p^r)$$.

This is because $p^2|p^r$ for $r\ge 2$.

Ok so this is what I think the solution is, and it looks logically consistent to me, I want to just see if it is correct so I upload my proof here. Any corrections would be appreciated.

Answer 1

Working to keep it simple we introduce

$$q(n) = \sum_{k=1, (n,k)=1}^n e^{2\pi i k/n}.$$

Now evidently

$$\sum_{d|n} \sum_{k=1, (n,k)=d}^n e^{2\pi i k/n} = \sum_{k=1}^n e^{2\pi i k/n}.$$

This evaluates to $1$ when $n=1$ and otherwise

$$e^{2\pi i/n} \sum_{k=0}^{n-1} e^{2\pi i k/n} = e^{2\pi i/n} \frac{1-e^{2\pi i}}{1-e^{2\pi i/n}} = 0.$$

Therefore with an Iverson bracket

$$\sum_{k=1}^n e^{2\pi i k/n} = [[ n=1 ]].$$

We also have

$$\sum_{d|n} \sum_{k=1, (n,k)=d}^n e^{2\pi i k/n} = \sum_{d|n} \sum_{k=1, (n/d,k)=1}^{n/d} e^{2\pi i k/(n/d)} \\ = \sum_{d|n} q(n/d) = \sum_{d|n} q(d).$$

Therefore we have by Mobius inversion

$$q(n) = \sum_{d|n} \mu(d) [[n/d = 1]] = \mu(n).$$

Remark. I just saw that this is in the comments by @reuns.

Answer 2

Your approach for tackling such famous Ramanujan sum looks fine, but I like to add an alternative derivation (shorter, if you already know the Moebius inversion formula). Let us assume $a>2$ (the cases $a\in\{1,2\}$ are straightforward to check). Your sum is just the sum of the primitive $a$-th roots of unity, i.e. the sum of the roots of $\Phi_a(x)$. This is a palyndromic polinomial, since it is a monic polynomial and if $\zeta$ is a primitive $a$-th root of unity, $\zeta^{-1}$ is a primitive $a$-th root of unity too. By invoking Vieta's theorem we get that our sum equals $-\Phi_{a}'(0)=-\left.\frac{d}{dx}\log\Phi_a(x)\right|_{x=0}$. By Moebius inversion formula we have $$ \Phi_a(x) = \prod_{d\mid a}(x^d-1)^{\mu(a/d)} $$ and by applying $\frac{d}{dx}\log(\cdot )$ to both sides: $$ \frac{\Phi_a'(x)}{\Phi_a(x)}=\sum_{d\mid a}\mu\left(\tfrac{a}{d}\right)\frac{d x^{d-1}}{x^d-1}. $$ When applying $\lim_{x\to 0}$ to both sides, the only term of the RHS potentially providing a non-zero contribution is the term associated with $d=1$. It follows that: $$ \sum_{\substack{1\leq n\leq a\\ \gcd(n,a)=1}}\!\!\!\exp\left(\tfrac{2\pi i n}{a}\right) = -\lim_{x\to 0}\mu\left(\tfrac{a}{1}\right)\frac{1}{x-1}=\color{red}{\mu(a)}$$ as wanted.