# Let $f(n) = \sum_{(k,n)=1} e^\frac{2\pi ik}{n}$. Show that $f(n) = \sum_{k=1}^{n}\left(\sum_{d\mid (k,n)} \mu(d)e^{\frac{2\pi ik}{n}} \right)$

I saw a proof for the above that went \begin{align*} f(n) &= \sum_{k=1}^{n}\left(\sum_{d\mid (k,n)} \mu(d)e^{\frac{2\pi ik}{n}} \right)\\ &= \sum_{d\mid n} \left( \mu(d) \sum_{k=0}^{(n/d)-1} e^{\frac{2\pi idk}{n}} \right), \end{align*} in which case for $$g(n)=\sum_{k=0}^{n-1} e^{\frac{2\pi ik}{n}}$$ we have $$\begin{equation*} f(n)=\sum_{d\mid n} \mu(d) g(n/d) \implies g(n) = \sum_{d\mid n} f(d), \end{equation*}$$ which then proves the statement above by Mobius Inversion once more, since $$g$$ is $$0$$ for all $$n>1$$.

I understand most of the proof; I'm just not sure how we went through the first two steps of transforming $$f(n)$$ to get to the point where we can apply the inversion. If anyone can explain the first two steps for me I would appreciate it, thanks!

We would do : $$f(n) = \sum_{\ \ \ k=1 \\(k,n) = 1}^n e^{\frac{2 \pi i k}n} = \sum_{k=1}^n 1_{\{(k,n) = 1\}}e^{\frac{2 \pi ik}n}$$ where $$1_X = 1$$ whenever something belongs in the set $$X$$ and $$0$$ otherwise.

Now use the basic inversion formula : $$\sum_{d | t} \mu(d) = 0$$ for any $$t \neq 1$$, and $$1$$for $$t = 1$$. That is, we have $$1_{\{t\}} = \sum_{d | t} \mu(d)$$. With this, we get : $$\sum_{k=1}^n \sum_{d | (k,n)} \mu(d)e^{\frac{2 \pi i k}n}$$

As the first line required.

For the second line, we do a "reindexing". See, the term $$\mu(d) e^{\frac{2 \pi i k}n}$$ is being first summed over all $$d$$ dividing $$(k,n)$$, and then running over all $$k=1$$ to $$n$$. Suppose we wanted to run over all $$k$$ first, then over all $$d$$. The question is , how would this be done?

It would be as follows : certainly $$d$$ must be a divisor of $$n$$, so $$d$$ can be allowed to run over all divisors of $$n$$, i.e. $$\sum_{d |n}$$ is justifiable. Now, fixing $$d$$, which $$k$$ can be such that $$d | (k,n)$$? Certainly those which are multiples of $$d$$! That is, numbers of the form $$d , 2d, ... , \frac{(n-1)d}{d}$$.

Let us take an example, say $$n=6$$. Let's go over all pairs $$(d,k)$$ for which $$\mu(d)e^{\frac{2\pi ik}{n}}$$ appears in the summation.

For $$k=1,5$$ we have $$d = 1$$. For $$k=2,4$$ we have $$d = 1,2$$. For $$k = 3$$ we have $$d = 1,3$$, and finally for $$k=6$$ we have $$d = 1,2,3,6$$.

Now, reverse it : for $$d =1$$ we have $$k=1,2,3,4,5,6$$. For $$d = 2$$ we have $$k = 2,4,6$$, for $$d = 3$$ we have $$k=3,6$$, for $$d = 6$$ we have $$k = 6$$. You can see the reindexing is exactly as I have described.

Thus, we do a reindexing : $$\sum_{k = 1}^n \sum_{d | (k,n)} \mu(d)e^{\frac{2 \pi i k}{n}} = \sum_{d | n} \sum_{k \textrm{ multiple of } d} \mu(d)e^{\frac{2 \pi ik}n} = \sum_{d | n} \sum_{l = 1}^{\frac{n}d -1} \mu(d) e^{\frac{2 \pi i dl}n}$$

as required.