# Analytic Number Theory/Formulas for number-theoretic functions
## Formulas for the Möbius μ function

Lemma 2.9:
    $\sum _{d|n}\mu (d){\frac {n}{d}}=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)$.
Proof:
For $\kappa \in \mathbb {Z} ^{r}$ a multiindex, $\alpha \in \{0,1\}^{r}$ and $Q\in \mathbb {C} ^{r}$ a vector define
    $Q^{\alpha }:=\prod _{j=1}^{r}q_{j}^{\alpha _{j}}$,
    $Q^{\kappa }:=(q_{1}^{k_{1}},\ldots ,q_{r}^{k_{r}})$.
Let $n=(P^{\kappa })^{1}=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. Then
    ${\begin{aligned}\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)&=\sum _{\alpha \in \{0,1\}^{r}}(P^{\kappa })^{\alpha }(P^{\kappa -1})^{1-\alpha }(-1)^{|}{1-\alpha |}\\&=\sum _{d|n}\mu (d){\frac {n}{d}}\end{aligned}}$.$\Box$
Lemma 2.10:
    $\varphi =\mu *I_{1}$.
Proof 1:
We prove the lemma from lemma 2.14.
We have by lemma 2.14
    ${\begin{aligned}\varphi (n)&=\sum _{k=1}^{n}\delta (\gcd(k,n))\\&=\sum _{k=1}^{n}\sum _{d|\gcd(k,n)}\mu (d)\\&=\sum _{d|n}\sum _{k=1}^{n}[d|k]\mu (d)\\&=\sum _{d|n}\sum _{j=1}^{n/d}\mu (d)\end{aligned}}$$\Box$
Proof 2:
We prove the lemma from the product formula for Euler's totient function and lemma 2.9. Indeed, for $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$
    $\varphi (n)=\prod _{j=1}^{r}(p_{j}^{k_{j}}-p_{j}^{k_{j}-1})=\mu *I_{1}$.$\Box$
Lemma 2.14:
    $E*\mu =\delta$.
Proof 1:
We use the Möbius inversion formula.
Indeed, $E(n)=\sum _{d|n}\delta (d)=1$, and hence $\delta =\mu *E$.$\Box$
Proof 2:
We use multiplicativity.
Indeed, for a prime $p$, $k\in \mathbb {N}$ we have
    $E*\mu (p^{k})=\sum _{j=0}^{k}\mu (p^{j})=\mu (1)+\mu (p)=0$,
and thus due to the multiplicativity of $\mu$ and $E$ $E*\mu (n)=0$ if $n$ contains at least one prime factor. Since further $E*\mu (1)=1$ the claim follows.$\Box$
Proof 3:
We prove the lemma by direct computation. Indeed, if $1\neq n=P^{\kappa }$, then
    ${\begin{aligned}E*\mu (n)&=\sum _{d|n}\mu (d)\\&=\sum _{\alpha \in \{0,1\}^{r}}\mu (P^{\alpha })\\&=\sum _{\beta \in \{0,1\}^{r-1}}\left(\mu (P^{(0,\beta )})+\mu (P^{(1,\beta )})\right)=0\end{aligned}}$.$\Box$
Proof 4:
We prove the lemma from the Binomial theorem and combinatorics.
Let $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. From combinatorics we note that for $m\leq r$, there exist ${\binom {m}{r}}$ distinct ways to pick a subset $I\subseteq \{1,\ldots ,r\}$ such that $|I|=m$. Define $\alpha _{I}=(\alpha _{1},\ldots ,\alpha _{r})\in \{0,1\}^{r}$ where $\alpha _{j}=1\Leftrightarrow j\in I$. Then, by the Binomial theorem
    ${\begin{aligned}E*\mu (n)&=\sum _{d|n}\mu (d)\\&=\sum _{I\subseteq \{1,\ldots ,r\}}\mu (P^{\alpha _{I}})\\&=\sum _{I\subseteq \{1,\ldots ,r\}}(-1)^{|I|}\\&=\sum _{j=0}^{r}{\binom {j}{r}}(-1)^{j}1^{j}=(1-1)^{r}=0\end{aligned}}$.$\Box$

## Formulas for Euler's totient function

Lemma 2.11 (Gauß 1801):
    $\forall n\in \mathbb {N} :n=\sum _{d|n}\varphi (d)$.
Proof 1:
We use the Möbius inversion formula, proven below without using this lemma, and lemma 2.10.
We have $\sum _{d|n}\varphi (d)=S_{\varphi }(n)$ and hence $\varphi =\mu *S_{\varphi }$ by the Möbius inversion formula. On the other hand,
    $\varphi (n)=\mu *I_{1}(n)$
by lemma 2.10.
Hence, we obtain $\mu *S_{\varphi }=\mu *I_{1}$, and by cancellation of $\mu$ (the arithmetic functions form an integral domain) we get the lemma.$\Box$
Proof 2:
We use the converse of the Möbius inversion formula, proven below without using this lemma, and lemma 2.10.
Since $\varphi (n)=\mu *I_{1}(n)$ by lemma 2.10, we obtain from the converse of the Möbius inversion formula that $I_{1}(n)=S_{\varphi }(n)$.$\Box$
Proof 3:
We prove the lemma by double counting.
We first note that there are $n$ many fractions of the form ${\frac {m}{n}}$, $1\leq m\leq n$.
We now prove that there are also $\sum _{d|n}\varphi (d)$ many fractions of this form. Indeed, each fraction ${\frac {m}{n}}$, $1\leq m\leq n$ can be reduced to ${\frac {b}{d}}$, where $\gcd(b,d)=1$. $d$ is a divisor of $n$, since it is obtained by dividing $n$. Furthermore, for each divisor $d$ of $n$ there exist precisely $\varphi (d)$ many such fractions by definition of $\varphi$.$\Box$
Proof 4:
We prove the lemma by the means of set theory.
Define $S_{n,d}:=\{1\leq l\leq n|\gcd(d,l)=1\}$. Then $S_{n,d}=\{dk|1\leq k\leq n/d,\gcd(k,n)=1\}=dS_{n/d,1}$. Since $|S_{n/d,1}|=\varphi (n/d)$ and $\{1,\ldots ,n\}$ is the disjoint union of the sets $S_{n,d},d|n$, we thus have
    $n=\sum _{d|n}|S_{n,d}|=\sum _{d|n}d\varphi \left({\frac {n}{d}}\right)$.$\Box$
The next theorem comprises one of the most important examples for a multiplicative function.
Theorem 2.12 (Euler 1761):
Euler's totient function is multiplicative.
Proof 1:
We prove the theorem using double counting (due to Kronecker).
By definition of $\varphi$, there are $\varphi (m)\varphi (n)$ sums of the form
    ${\frac {k}{m}}+{\frac {l}{n}},1\leq k\leq m,1\leq l\leq n$,
where both summands are reduced. We claim that there is a bijection
    $\left\{{\frac {k}{m}}+{\frac {l}{n}}{\big |}1\leq k\leq m,1\leq l\leq n,{\frac {k}{m}},{\frac {l}{n}}{\text{ reduced}}\right\}\to \left\{{\frac {r}{mn}}{\big |}1\leq r\leq {\frac {r}{mn}}{\text{ reduced}}\right\}$.
From this would follow $\varphi (m)\varphi (n)=\varphi (mn)$.
We claim that such a bijection is given by ${\frac {k}{m}}+{\frac {l}{n}}\mapsto {\frac {nk+ml\mod mn}{nm}}$.
Well-definedness: Let ${\frac {k}{m}}$, ${\frac {l}{n}}$ be reduced. Then
    ${\frac {k}{m}}+{\frac {l}{n}}={\frac {kn+lm\mod mn}{nm}}$
is also reduced, for if $p|(nm)$, then without loss of generality $p|n$, and from $p|(kn+lm-cnm)$ follows $p|l$ or $p|m$. In both cases we obtain a contradiction, either to $\gcd(m,n)=1$ or to ${\frac {l}{n}}$ is reduced.
Surjectivity: Let ${\frac {r}{mn}}$ be reduced. Using the Euclidean algorithm, we find $a,b\in \mathbb {N}$ such that $an+bm=1$. Then $ran+rbm=r$. Define $k=ra\mod m$, $l=rb\mod n$. Then
    $kn+lm=(ra+tm)n+(rb+sn)m\equiv r\mod mn$.
Injectivity: Let $kn+lm\equiv k'n+l'm\mod mn$. We show $k=k'$; the proof for $l=l'$ is the same.
Indeed, from $kn+lm\equiv k'n+l'm\mod mn$ follows $kn\equiv k'n\mod m$, and since $\gcd(m,n)=1$, $n$ is invertible modulo $m$, which is why we may multiply this inverse on the right to obtain $k\equiv k'\mod m$. Since $1\leq k,k'\leq m$, the claim follows.$\Box$
Proof 2:
We prove the theorem from the Chinese remainder theorem.
Let $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. From the Chinese remainder theorem, we obtain a ring isomorphism
    $\mathbb {Z} /n\to \mathbb {Z} /p_{1}^{k_{1}}\times \cdots \times \mathbb {Z} /p_{r}^{k_{r}}$,
which induces a group isomorphism
    $(\mathbb {Z} /n)^{\times }\to \left(\mathbb {Z} /p_{1}^{k_{1}}\right)^{\times }\times \cdots \times \left(\mathbb {Z} /p_{r}^{k_{r}}\right)^{\times }$.
Hence, $\left|(\mathbb {Z} /n)^{*}\right|=\prod _{j=1}^{r}\left|\left(\mathbb {Z} /p_{j}^{k_{j}}\right)^{*}\right|$, and from $\forall m\in \mathbb {N} :\varphi (m)=\left|(\mathbb {Z} /m)^{*}\right|$ follows the claim.$\Box$
Proof 3: We prove the theorem from lemma 2.11 and induction (due to Hensel).
Let $m,n\in \mathbb {N}$ such that $\gcd(m,n)=1$. By lemma 2.11, we have $m=\sum _{e|m}\varphi (e)$ and $n=\sum _{d|m}\varphi (d)$ and hence
    $mn=\varphi (m)\varphi (n)+\varphi (m)\sum _{d|n,d<n}\varphi (d)+\varphi (n)\sum _{e|m,e<m}\varphi (e)+\sum _{d|n,e|m \atop d<n,e<m}\varphi (d)\varphi (e)$.
Furthermore, by lemma 2.11 and the bijection from the proof of theorem 2.8,
    $mn=\sum _{f|mn}\varphi (f)=\sum _{e|m,d|n}\varphi (ed)$.
By induction on $ed,en,md<mn$ we thus have
    $mn=\varphi (mn)+\varphi (m)\sum _{d|n}\varphi (d)+\varphi (n)\sum _{e|m}\varphi (e)+\sum _{e|m,d|n \atop e<m,d<n}\varphi (e)\varphi (d)$.$\Box$
Proof 4: We prove the theorem from lemma 2.11 and the Möbius inversion formula.
Indeed, from lemma 2.10 and the Möbius inversion formula, we obtain
    $\varphi =\mu *I_{1}$,
which is why $\varphi$ is multiplicative as the convolution of two multiplicative functions.$\Box$
Proof 5: We prove the theorem from Euler's product formula.
Indeed, if $m=P^{\kappa }$ and $n=Q^{\iota }$ and $\gcd(m,n)=1$, then $P\cap Q=\emptyset$ and hence
    $\prod _{p|n}(p^{\kappa _{p}}-p^{\kappa _{p}-1})\prod _{q|n}(q^{\iota }-q^{\iota _{q}-1})=\varphi (mn)$.$\Box$
Theorem 2.15 (Möbius inversion formula):
Let $f$ be an arithmetical function and define
    $S_{f}(n):=\sum _{d|n}f(d)=f*E(n)$.
Then
    $f=\mu *S_{f}=\sum _{d|n}\mu (d)S_{f}\left({\frac {n}{d}}\right)$.
Proof:
By lemma 2.14 and associativity of convolution,
    $\mu *S_{f}=\mu *f*E=\mu *E*f=\delta *f=f$.$\Box$
Theorem 2.16 (Product formula for Euler's totient function):
Let $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, where $p_{1},\ldots ,p_{r}$ are pairwise different prime numbers and $k_{1},\ldots ,k_{r}\in \mathbb {N}$ (recall that every number has such a decomposition by the fundamental theorem of arithmetic. Then
    $\varphi (n)=n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)$.
Proof 1:
We prove the theorem from lemma 2.10 and the fact that $\varphi$ is multiplicative.
Indeed, let $p$ be a prime number and let $k\in \mathbb {N}$. Then $\varphi (p^{k})=p^{k}-p^{k-1}$, since
    $\varphi (p^{k})=(\mu *I_{1})(p^{k})=\sum _{j=0}^{k}\mu (p^{j})p^{k-j}$
by lemma 2.10. Therefore,
    $\varphi (n)=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)=n\prod _{j=1}^{r}$,
where the latter equation follows from
    ${\begin{aligned}n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)&=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)\\&=\prod _{j=1}^{r}p_{j}^{k_{j}}\left(1-{\frac {1}{p_{j}}}\right)\\&=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)\end{aligned}}$.$\Box$
Proof 2:
We prove the identity by the means of probability theory.
Let $n\in \mathbb {N}$, $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. Choose $\Omega =\{1,\ldots ,n\}$, ${\mathcal {F}}=2^{\Omega }$, $P(A):={\frac {|A|}{n}}$. For $j\in \{1,\ldots ,r\}$ define the event $E_{p_{j}}:=\{1\leq k\leq n|p_{j}|n\}$. Then we have
    $P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)={\frac {\varphi (n)}{n}}$.
On the other hand, for each $J=\{j_{1},\ldots ,j_{l}\}\subseteq \{1,\ldots ,r\}$, we have
    ${\begin{aligned}P\left(E_{p_{j_{1}}}\cap \cdots \cap E_{p_{j_{1}}}\right)&=P\left(\left\{1\leq k\leq n{\big |}\prod _{j\in J}p_{j}|k\right\}\right)\\&={\frac {1}{\prod _{j\in J}p_{j}}}=\prod _{j\in J}P\left(E_{p_{j}}\right)\end{aligned}}$.
Thus, it follows that $E_{p_{1}},\ldots ,E_{p_{r}}$ are independent. But since events are independent if and only if their complements are, we obtain
    ${\frac {\varphi (n)}{n}}=P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)=P\left({\overline {E_{p_{1}}}})\right)\cdots P\left({\overline {E_{p_{r}}}}\right)=\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)$.$\Box$
Proof 3:
We prove the identity from the Möbius inversion formula and lemmas 2.9 and 2.10.
But by the Möbius inversion formula and since by lemma 2.10 $S_{\varphi }=I_{1}$,
    $\sum _{d|n}\mu (d){\frac {n}{d}}=\mu *S_{\varphi }(n)=\varphi (n)$.$\Box$
Proof 4:
We prove the identity from the inclusion–exclusion principle.
Indeed, by one of de Morgan's rules and the inclusion–exclusion principle we have for sets $A_{1},\ldots ,A_{r}\subseteq S$
    ${\begin{aligned}\left|\bigcap _{j=1}^{r}A_{j}\right|&=\left|S\setminus \bigcup _{j=1}^{r}\left(S\setminus A_{j}\right)\right|\\&=|S|-\left|\bigcup _{j=1}^{r}\left(S\setminus A_{j}\right)\right|\\&=|S|+\sum _{\emptyset \neq J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|\\&=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|\end{aligned}}$,
where we use the convention that the empty intersection equals the universal set $S$. Let now $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, and define $S=\{m|1\leq m\leq n\}$ and $A_{j}:=\{l\in S|p_{j}\not |l\}$ for $1\leq j\leq r$. Since
    $\varphi (n)=\left|\bigcap _{j=1}^{r}A_{j}\right|$,
we then have
    $\varphi (n)=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|$.
But for each $J\subseteq \{1,\ldots ,r\}$, we have
    ${\begin{aligned}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|&=\left\{1\leq l\leq n{\big |}\forall j\in J:p_{j}|l\right\}\\&=\left\{1\leq l\leq n{\big |}\left(\prod _{j\in J}p_{j}\right)|l\right\}={\frac {n}{\prod _{j\in J}p_{j}}}\end{aligned}}$.
It follows
    $\varphi (n)=n\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}$,
and since
    $\prod {m=1}^{r}\left(1-{\frac {1}{p_{m}}}\right)=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}$,
the theorem is proven.$\Box$

### Exercises
## Formulas for the von Mangoldt function

Theorem 8.? (The Selberg identity):