# Analytic Number Theory/Formulas for number-theoretic functions

## Formulas for the Möbius μ function

Lemma 2.9:

${\displaystyle \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 ${\displaystyle \kappa \in \mathbb {Z} ^{r}}$ a multiindex, ${\displaystyle \alpha \in \{0,1\}^{r}}$ and ${\displaystyle Q\in \mathbb {C} ^{r}}$ a vector define

${\displaystyle Q^{\alpha }:=\prod _{j=1}^{r}q_{j}^{\alpha _{j}}}$,
${\displaystyle Q^{\kappa }:=(q_{1}^{k_{1}},\ldots ,q_{r}^{k_{r}})}$.

Let ${\displaystyle n=(P^{\kappa })^{1}=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$. Then

{\displaystyle {\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}}}.${\displaystyle \Box }$

Lemma 2.10:

${\displaystyle \varphi =\mu *I_{1}}$.

Proof 1:

We prove the lemma from lemma 2.14.

We have by lemma 2.14

{\displaystyle {\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}}}${\displaystyle \Box }$

Proof 2:

We prove the lemma from the product formula for Euler's totient function and lemma 2.9. Indeed, for ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$

${\displaystyle \varphi (n)=\prod _{j=1}^{r}(p_{j}^{k_{j}}-p_{j}^{k_{j}-1})=\mu *I_{1}}$.${\displaystyle \Box }$

Lemma 2.14:

${\displaystyle E*\mu =\delta }$.

Proof 1:

We use the Möbius inversion formula.

Indeed, ${\displaystyle E(n)=\sum _{d|n}\delta (d)=1}$, and hence ${\displaystyle \delta =\mu *E}$.${\displaystyle \Box }$

Proof 2:

We use multiplicativity.

Indeed, for a prime ${\displaystyle p}$, ${\displaystyle k\in \mathbb {N} }$ we have

${\displaystyle E*\mu (p^{k})=\sum _{j=0}^{k}\mu (p^{j})=\mu (1)+\mu (p)=0}$,

and thus due to the multiplicativity of ${\displaystyle \mu }$ and ${\displaystyle E}$ ${\displaystyle E*\mu (n)=0}$ if ${\displaystyle n}$ contains at least one prime factor. Since further ${\displaystyle E*\mu (1)=1}$ the claim follows.${\displaystyle \Box }$

Proof 3:

We prove the lemma by direct computation. Indeed, if ${\displaystyle 1\neq n=P^{\kappa }}$, then

{\displaystyle {\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}}}.${\displaystyle \Box }$

Proof 4:

We prove the lemma from the Binomial theorem and combinatorics.

Let ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$. From combinatorics we note that for ${\displaystyle m\leq r}$, there exist ${\displaystyle {\binom {m}{r}}}$ distinct ways to pick a subset ${\displaystyle I\subseteq \{1,\ldots ,r\}}$ such that ${\displaystyle |I|=m}$. Define ${\displaystyle \alpha _{I}=(\alpha _{1},\ldots ,\alpha _{r})\in \{0,1\}^{r}}$ where ${\displaystyle \alpha _{j}=1\Leftrightarrow j\in I}$. Then, by the Binomial theorem

{\displaystyle {\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}}}.${\displaystyle \Box }$

## Formulas for Euler's totient function

Lemma 2.11 (Gauß 1801):

${\displaystyle \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 ${\displaystyle \sum _{d|n}\varphi (d)=S_{\varphi }(n)}$ and hence ${\displaystyle \varphi =\mu *S_{\varphi }}$ by the Möbius inversion formula. On the other hand,

${\displaystyle \varphi (n)=\mu *I_{1}(n)}$

by lemma 2.10.

Hence, we obtain ${\displaystyle \mu *S_{\varphi }=\mu *I_{1}}$, and by cancellation of ${\displaystyle \mu }$ (the arithmetic functions form an integral domain) we get the lemma.${\displaystyle \Box }$

Proof 2:

We use the converse of the Möbius inversion formula, proven below without using this lemma, and lemma 2.10.

Since ${\displaystyle \varphi (n)=\mu *I_{1}(n)}$ by lemma 2.10, we obtain from the converse of the Möbius inversion formula that ${\displaystyle I_{1}(n)=S_{\varphi }(n)}$.${\displaystyle \Box }$

Proof 3:

We prove the lemma by double counting.

We first note that there are ${\displaystyle n}$ many fractions of the form ${\displaystyle {\frac {m}{n}}}$, ${\displaystyle 1\leq m\leq n}$.

We now prove that there are also ${\displaystyle \sum _{d|n}\varphi (d)}$ many fractions of this form. Indeed, each fraction ${\displaystyle {\frac {m}{n}}}$, ${\displaystyle 1\leq m\leq n}$ can be reduced to ${\displaystyle {\frac {b}{d}}}$, where ${\displaystyle \gcd(b,d)=1}$. ${\displaystyle d}$ is a divisor of ${\displaystyle n}$, since it is obtained by dividing ${\displaystyle n}$. Furthermore, for each divisor ${\displaystyle d}$ of ${\displaystyle n}$ there exist precisely ${\displaystyle \varphi (d)}$ many such fractions by definition of ${\displaystyle \varphi }$.${\displaystyle \Box }$

Proof 4:

We prove the lemma by the means of set theory.

Define ${\displaystyle S_{n,d}:=\{1\leq l\leq n|\gcd(d,l)=1\}}$. Then ${\displaystyle S_{n,d}=\{dk|1\leq k\leq n/d,\gcd(k,n)=1\}=dS_{n/d,1}}$. Since ${\displaystyle |S_{n/d,1}|=\varphi (n/d)}$ and ${\displaystyle \{1,\ldots ,n\}}$ is the disjoint union of the sets ${\displaystyle S_{n,d},d|n}$, we thus have

${\displaystyle n=\sum _{d|n}|S_{n,d}|=\sum _{d|n}d\varphi \left({\frac {n}{d}}\right)}$.${\displaystyle \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 ${\displaystyle \varphi }$, there are ${\displaystyle \varphi (m)\varphi (n)}$ sums of the form

${\displaystyle {\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

${\displaystyle \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 ${\displaystyle \varphi (m)\varphi (n)=\varphi (mn)}$.

We claim that such a bijection is given by ${\displaystyle {\frac {k}{m}}+{\frac {l}{n}}\mapsto {\frac {nk+ml\mod mn}{nm}}}$.

Well-definedness: Let ${\displaystyle {\frac {k}{m}}}$, ${\displaystyle {\frac {l}{n}}}$ be reduced. Then

${\displaystyle {\frac {k}{m}}+{\frac {l}{n}}={\frac {kn+lm\mod mn}{nm}}}$

is also reduced, for if ${\displaystyle p|(nm)}$, then without loss of generality ${\displaystyle p|n}$, and from ${\displaystyle p|(kn+lm-cnm)}$ follows ${\displaystyle p|l}$ or ${\displaystyle p|m}$. In both cases we obtain a contradiction, either to ${\displaystyle \gcd(m,n)=1}$ or to ${\displaystyle {\frac {l}{n}}}$ is reduced.

Surjectivity: Let ${\displaystyle {\frac {r}{mn}}}$ be reduced. Using the Euclidean algorithm, we find ${\displaystyle a,b\in \mathbb {N} }$ such that ${\displaystyle an+bm=1}$. Then ${\displaystyle ran+rbm=r}$. Define ${\displaystyle k=ra\mod m}$, ${\displaystyle l=rb\mod n}$. Then

${\displaystyle kn+lm=(ra+tm)n+(rb+sn)m\equiv r\mod mn}$.

Injectivity: Let ${\displaystyle kn+lm\equiv k'n+l'm\mod mn}$. We show ${\displaystyle k=k'}$; the proof for ${\displaystyle l=l'}$ is the same.

Indeed, from ${\displaystyle kn+lm\equiv k'n+l'm\mod mn}$ follows ${\displaystyle kn\equiv k'n\mod m}$, and since ${\displaystyle \gcd(m,n)=1}$, ${\displaystyle n}$ is invertible modulo ${\displaystyle m}$, which is why we may multiply this inverse on the right to obtain ${\displaystyle k\equiv k'\mod m}$. Since ${\displaystyle 1\leq k,k'\leq m}$, the claim follows.${\displaystyle \Box }$

Proof 2:

We prove the theorem from the Chinese remainder theorem.

Let ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$. From the Chinese remainder theorem, we obtain a ring isomorphism

${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /p_{1}^{k_{1}}\times \cdots \times \mathbb {Z} /p_{r}^{k_{r}}}$,

which induces a group isomorphism

${\displaystyle (\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, ${\displaystyle \left|(\mathbb {Z} /n)^{*}\right|=\prod _{j=1}^{r}\left|\left(\mathbb {Z} /p_{j}^{k_{j}}\right)^{*}\right|}$, and from ${\displaystyle \forall m\in \mathbb {N} :\varphi (m)=\left|(\mathbb {Z} /m)^{*}\right|}$ follows the claim.${\displaystyle \Box }$

Proof 3: We prove the theorem from lemma 2.11 and induction (due to Hensel).

Let ${\displaystyle m,n\in \mathbb {N} }$ such that ${\displaystyle \gcd(m,n)=1}$. By lemma 2.11, we have ${\displaystyle m=\sum _{e|m}\varphi (e)}$ and ${\displaystyle n=\sum _{d|m}\varphi (d)}$ and hence

${\displaystyle mn=\varphi (m)\varphi (n)+\varphi (m)\sum _{d|n,d.

Furthermore, by lemma 2.11 and the bijection from the proof of theorem 2.8,

${\displaystyle mn=\sum _{f|mn}\varphi (f)=\sum _{e|m,d|n}\varphi (ed)}$.

By induction on ${\displaystyle ed,en,md we thus have

${\displaystyle mn=\varphi (mn)+\varphi (m)\sum _{d|n}\varphi (d)+\varphi (n)\sum _{e|m}\varphi (e)+\sum _{e|m,d|n \atop e.${\displaystyle \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

${\displaystyle \varphi =\mu *I_{1}}$,

which is why ${\displaystyle \varphi }$ is multiplicative as the convolution of two multiplicative functions.${\displaystyle \Box }$

Proof 5: We prove the theorem from Euler's product formula.

Indeed, if ${\displaystyle m=P^{\kappa }}$ and ${\displaystyle n=Q^{\iota }}$ and ${\displaystyle \gcd(m,n)=1}$, then ${\displaystyle P\cap Q=\emptyset }$ and hence

${\displaystyle \prod _{p|n}(p^{\kappa _{p}}-p^{\kappa _{p}-1})\prod _{q|n}(q^{\iota }-q^{\iota _{q}-1})=\varphi (mn)}$.${\displaystyle \Box }$

Theorem 2.15 (Möbius inversion formula):

Let ${\displaystyle f}$ be an arithmetical function and define

${\displaystyle S_{f}(n):=\sum _{d|n}f(d)=f*E(n)}$.

Then

${\displaystyle 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,

${\displaystyle \mu *S_{f}=\mu *f*E=\mu *E*f=\delta *f=f}$.${\displaystyle \Box }$

Theorem 2.16 (Product formula for Euler's totient function):

Let ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$, where ${\displaystyle p_{1},\ldots ,p_{r}}$ are pairwise different prime numbers and ${\displaystyle k_{1},\ldots ,k_{r}\in \mathbb {N} }$ (recall that every number has such a decomposition by the fundamental theorem of arithmetic. Then

${\displaystyle \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 ${\displaystyle \varphi }$ is multiplicative.

Indeed, let ${\displaystyle p}$ be a prime number and let ${\displaystyle k\in \mathbb {N} }$. Then ${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}$, since

${\displaystyle \varphi (p^{k})=(\mu *I_{1})(p^{k})=\sum _{j=0}^{k}\mu (p^{j})p^{k-j}}$

by lemma 2.10. Therefore,

${\displaystyle \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

{\displaystyle {\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}}}.${\displaystyle \Box }$

Proof 2:

We prove the identity by the means of probability theory.

Let ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$. Choose ${\displaystyle \Omega =\{1,\ldots ,n\}}$, ${\displaystyle {\mathcal {F}}=2^{\Omega }}$, ${\displaystyle P(A):={\frac {|A|}{n}}}$. For ${\displaystyle j\in \{1,\ldots ,r\}}$ define the event ${\displaystyle E_{p_{j}}:=\{1\leq k\leq n|p_{j}|n\}}$. Then we have

${\displaystyle P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)={\frac {\varphi (n)}{n}}}$.

On the other hand, for each ${\displaystyle J=\{j_{1},\ldots ,j_{l}\}\subseteq \{1,\ldots ,r\}}$, we have

{\displaystyle {\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 ${\displaystyle E_{p_{1}},\ldots ,E_{p_{r}}}$ are independent. But since events are independent if and only if their complements are, we obtain

${\displaystyle {\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)}$.${\displaystyle \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 ${\displaystyle S_{\varphi }=I_{1}}$,

${\displaystyle \sum _{d|n}\mu (d){\frac {n}{d}}=\mu *S_{\varphi }(n)=\varphi (n)}$.${\displaystyle \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 ${\displaystyle A_{1},\ldots ,A_{r}\subseteq S}$

{\displaystyle {\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 ${\displaystyle S}$. Let now ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$, and define ${\displaystyle S=\{m|1\leq m\leq n\}}$ and ${\displaystyle A_{j}:=\{l\in S|p_{j}\not |l\}}$ for ${\displaystyle 1\leq j\leq r}$. Since

${\displaystyle \varphi (n)=\left|\bigcap _{j=1}^{r}A_{j}\right|}$,

we then have

${\displaystyle \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 ${\displaystyle J\subseteq \{1,\ldots ,r\}}$, we have

{\displaystyle {\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

${\displaystyle \varphi (n)=n\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}}$,

and since

${\displaystyle \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.${\displaystyle \Box }$

## Formulas for the von Mangoldt function

Theorem 8.? (The Selberg identity):