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!
 A: 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.
