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$

Formulas for the von Mangoldt function

Theorem 8.? (The Selberg identity):