Möbius inversion and Möbius function as sum of cosines Let $\mu (n)$ be the Möbius function. I want to prove the following formula:
$$\mu (n)=\sum_{\substack{1\leq k \leq n\\ (k,n)=1}}\cos \frac{2k\pi}{n}.$$
Let $F(n)$ be the right hand side, then by Möbius Inversion, it suffices to show that $(F*1)(n)=\delta(n)$, where $*$ is the dirichlet convolution, $1(n)=1$ is the constant function and $\delta (n)=1$ if $n=1$ and $0$ otherwise is the delta function.
Now, $$(F*1)(n)=\sum_{d|n}\sum_{\substack{1\leq k \leq d\\ (k,d)=1}}\cos \frac{2k\pi}{d}$$
$$=\sum_{d|n}\sum_{\substack{1\leq k \leq d\\ (k,d)=1}}\cos \frac{2ke\pi}{ed}=\sum_{d|n}\sum_{\substack{1\leq k \leq d\\ (k,d)=1}}\cos \frac{2ke\pi}{n}$$,
where $e=n/d \in \mathbb{N}$.
I want to show that the above sum is equal to
$\sum_{j=1}^n\cos \frac{2j\pi}{n}$ and the result will follow quickly as $\sum_{j=1}^n\cos \frac{2j\pi}{n} = \sum_{j=1}^n \operatorname{Re}\zeta_n^{j}$ where $\zeta_n=e^{2\pi i/n}$ is the primitive $n$-th root of unity.
To this end, it suffices to show that there is a bijection between the two sets:
$S_1:=\{kn/d| 1\leq k \leq d, (k,d)=1, d|n\}$ and $S_2:=\{1,2\cdots, n\}$.
Now $S_1 \subseteq S_2$ is clear, however I have a hard time proving the other inclusion: for any $l\in S_2$, if $(l,d)=q$, then we set $k=l/q$ such that $(k,d)=1$ and we have $nk/d=nl/dq$ and we are done if we can show $dq=n$.
Actually this is problem 4.13 from the following handout https://web.evanchen.cc/handouts/Summation/Summation.pdf and I wonder if there is any quicker way since my method seems a bit overly complicated.
Thank you so much in advance.
 A: If you divide all the elements of $S_1$ and $S_2$ by $n$, you get the sets
$$
\tfrac1nS_1 = \{ \tfrac kd\colon 1\le k\le d,\, (k,d)=1,\, d\mid n\} \quad\text{and}\quad \tfrac1nS_2 = \{ \tfrac jn\colon 1\le j\le n\}.
$$
But here it's actually clear that the two sets are in bijection: the elements of $\frac1nS_1$ are simply the reduced-to-lowest-terms forms of the elements of $\frac1nS_2$! (This is the same trick used to prove the identity $\sum_{d\mid n} \phi(d) = n$.)
A: Another approach. You may notice that
$$ S(n)=\sum_{\substack{1\leq k\leq n\\(k,n)=1}}\exp\left(2\pi i \frac{k}{n}\right)$$
literally is the sum of the primitive $n$-th roots of unity, i.e. the sum of the roots of the cyclotomic polynomial $\Phi_n(x)$.
Assuming $n>1$ we have that $\Phi_n(x)$ is palyndromic, $\Phi_n(x) = x^{\varphi(n)}\Phi_n(1/x)$, since if $\zeta$ is a primitive root of unity then $1/\zeta$ is also a primitive root of unity. By Vieta's theorem the sum of the roots is given by the opposite of the coefficient of $x^{\varphi(n)-1}$ in $\Phi_n(x)$, which by symmetry is also the coefficient of $x$. This leads to
$$ S(n) = -\Phi_n'(0) = -\left. \frac{d}{dx}\log\Phi_n(x)\right|_{x=0}. $$
By the inclusion/exclusion principle or by Moebius inversion formula we have
$$ \Phi_n(x) = \prod_{d\mid n}(x^{d}-1)^{\mu(n/d)} $$
so
$$ \log\Phi_n(x) = \sum_{d\mid n}\mu(n/d)\log(x^d-1) $$
$$ \frac{d}{dx}\log\Phi_n(x) = \sum_{d\mid n}\mu(n/d)\frac{dx^{d-1}}{x^d-1} $$
and the evaluation at $x=0$ annihilates all the terms of the RHS, except the first one associated to $d=1$. This proves $S(n)=\mu(n)$ and by considering the real part of the sum defining $S(n)$ you have your claim.
A: Let $e(s)=e^{2\pi is}$, then it suffices to show that
$$
S_n=\sum_{\substack{1\le k\le n\\(k,n)=1}}e(k/n)=\mu(n).
$$
Using the fact that
$$
\sum_{d|n}\mu(d)=
\begin{cases}
1 & n=1 \\
0 & n>1
\end{cases},
$$
we have
$$
S_n=\sum_{d|n}\mu(d)\sum_{\substack{1\le k\le n\\d|k}}e(k/n)=\sum_{d|n}\mu(d)\sum_{1\le j\le n/d}e\left(j\over n/d\right).
$$
By the properties of the $e(s)$, we observe the rightmost sum is zero whenever $d<n$, so we have
$$
S_n=\sum_{\substack{d|n\\d=n}}\mu(d)\frac nd=\mu(n).
$$
A: This problem is an example of the old adage that the shortest path between two things in the real numbers often goes through the complex numbers.
In field theory, if $\zeta_n$ is a primitive $n$th root of unity then ${\rm Tr}_{\mathbf Q(\zeta_n)/\mathbf Q}(\zeta_n) = \mu(n)$. (See Jack’s answer.) That trace is the sum of roots of the minimal polynomial of $\zeta_n$ over $\mathbf Q$, and that sum is $\sum_{(k,n)=1} \zeta_n^k$, where the sum runs over all $k$ from $1$ to $n$ that are relatively prime to $n$.
Using $\zeta_n = e^{2\pi i/n}$, we get
$$
\sum_{(k,n)=1} e^{2\pi ik/n} = \mu(n).
$$
Now take the real parts of both sides.
A: It is a special case of a more general formula. Let $F\left(n\right)=\sum_{d|n}f\left(d\right)$. Then
$$F\left(\gcd(n,k)\right)=\sum_{d|\gcd(n,k)}f\left(d\right)=\sum_{d|n\\d|k}f\left(d\right)$$
By multiplying by $\exp \left(\frac{ i 2 \pi k}n \right)$ and summation over $k$ we will get the more general formula
$$f\left(n\right)=\sum_{k=1}^{n}F\left(\gcd(n,k)\right)\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$
Using $f(n)=\mu(n)$ and $F(n)=e(n)$ you will get your formula
$$\mu\left(n\right)=\sum_{ {k=1}\\{(n,k)=1}}^{n}\exp \left(\frac{i 2 \pi k}n \right)=\sum_{{k=1}\\(n,k)=1}^{n}\cos \left(\frac{2 \pi k}n \right)$$
Using $f(n)=\phi(n)$ and $F(n)=n$  you will get the famous Schramm formula for the totient function
$$\phi\left(n\right)=\sum_{ {k=1}}^{n}\gcd(n,k)\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$
Using another pairs $F$ and $f$ you will get formulae for the absolute value of $\mu$
$$|\mu\left(n\right)|=\sum_{ {k=1}}^{n}\frac {\phi(n\cdot k)}{\phi(k)}\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$
for the Dirichlet inverse of $\phi$
$$\phi^{-1}\left(n\right)=\sum_{ {k=1}}^{n}\frac n{\gcd(n,k)}\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$
for the von Mangoldt function
$$\Lambda\left(n\right)=\sum_{ {k=1}}^{n}\ln\left(\gcd(n,k)\right)\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$
etc.
A: The $3$rd equation line, where you introduced the variable $e$, is not necessary and it could be removed without affecting the argument. Also note the term $\zeta_n$ in your question is not a primitive $n$th root of unity, but just a general $n$th root of unity.
As you correctly state we need to show the double summation in the $2$nd equation line equals $\sum_{j=1}^n\cos \frac{2j\pi}{n}$, and that to do that it suffices to show that the two sets $S_1$ and $S_2$ are equal. The $S_1 \subseteq S_2$ part is straightforward, however the other direction is not so obvious, but it can be arrived at by making use of the totient function $\phi$.
Instead of showing $S_2 \subseteq S_1$ to complete the proof of $S_1 = S_2$, since we are dealing with finite sets we can instead show $|S_1| = |S_2|$, ie. $|S_1| = n$, since we already know $S_1 \subseteq S_2$.
So, using a slightly different definition from yours, for a fixed $n \geq 1$ let :
\begin{eqnarray*}
S_1 & = & \{\textstyle{\frac{k}{d}} : d \mid n, k \in [1, d], (k, d) = 1 \}, \\
S_2 & = & \{ \textstyle{\frac{j}{n}} : j \in [1, n] \}
\end{eqnarray*}
We can write $S_1$ as a union of the subsets $S_1^{(d)}$ that come from particular divisors $d$ of $n$ :
$$
S_1 = \bigcup_{d \mid n} S_1^{(d)}
$$
where, with $n \geq 1$ fixed and $d$ a divisor of $n$ :
$$
S_1^{(d)} = \{ \textstyle{\frac{k}{d}} : k \in [1, d], (k, d) = 1 \}.
$$
Then we have $|S_1^{(d)}| = \phi(d) \; \forall d$, and so if the $S_1^{(d)}$'s are mutually disjoint, forming a partition of $S_1$, then using the divisor sum of the totient (eg here or [1, p26, Theorem 2.2]) :
$$
|S_1| = \sum_{d \mid n} |S_1^{(d)}| = \sum_{d \mid n} \phi(d) = n = |S_2|
$$
as required. Thus it suffices to show the $S_1^{(d)}$'s are mutually disjoint. Consider an $x \in S_1^{(d_1)} \cap S_1^{(d_2)}$. Then there exists $k_1 \in [1, d_1]$ with $(k_1, d_1) = 1$, and $k_2 \in [1, d_2]$ with $(k_2, d_2) = 1$ such that :
$$
x = \frac{k_1}{d_1} = \frac{k_2}{d_2}.
$$
But these are fractions in their simplest form so their numerators and denominators must be the same, due to the uniqueness of the simplest form of a fraction, and hence in particular $d_1 = d_2$. Thus the $S_1^{(d)}$'s are mutually disjoint. Alternatively we could say $k_1 d_2 = k_2 d_1$ and then in terms of the 'multisets' which are the prime decompositions, the primes of $d_2$ must all be contained within $d_1$, as $d_2$ shares no primes with $k_2$, so that '$d_2 \subseteq d_1$', and likewise as $d_1$ shares no primes with $k_1$, so '$d_1 \subseteq d_2$', and thus $d_1 = d_2$ - which is how the uniqueness of the simplest form is proved.
The same method of proving $S_1 = S_2$ can be used to solve a more general problem (see [1, Problem 2.14, p48]), namely if :
\begin{eqnarray*}
F(n) & = & \sum_{k = 1}^n f(k/n) \\
\mbox{and} \hspace{2em} F^*(n) & = & \sum_{ \substack{k = 1 \\ (k, n) = 1} }^n f(k/n)
\end{eqnarray*}
then $F$ and $F^*$ are related by $F^* = \mu * F$.
From this we can arrive at the following relation for the sum of the primitive $n$th roots of unity (from which the relation you require can be deduced by taking the real part) :
$$
\sum_{ \substack{k = 1 \\ (k, n) = 1} }^n e^{2 \pi i k / n} = \mu(n), \hspace{3em} \forall n \geq 1
$$
by putting $f(x) = e^{2 \pi i x}$, so that the LHS is $F^*(n)$ and :
$$
F(n) = \sum_{k = 1}^n e^{2 \pi i k / n} \hspace{1em} = \mbox{sum of $n^{\mathrm{th}}$ roots of unity.}
$$
But for $n > 1$, the sum of the $n$th roots of unity $\{ \alpha_r \}$ is minus the coefficient of $z^{n - 1}$ in the complex polynomial $z^n - 1 = (z - \alpha_1) \cdots (z - \alpha_n)$, thus :
$$
F(n) = \left\{
\begin{array}{ll}
1, & \mbox{when $n = 1$}, \\
0, & \mbox{when $n > 1$}
\end{array}
\right.
$$
which equals the identity $\delta$ in the Dirichlet ring, and hence $F^* = \mu$, as required.
References
[1] Tom M. Apostol (1976), Introduction to Analytic Number Theory, Springer-Verlag.
