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(p_j^{k_j}-p_j^{k_j-1})$.

Proof:

For $\kappa \in {\mathbb{Z}}^r$ a multiindex, $\alpha \in \{0,1{\}}^r$ and $Q\in {ℂ}^r$ a vector define

$Q^{\alpha }:=\prod _{j=1}^r{q}_j^{{\alpha }_j}$,

$Q^{\kappa }:=(q_1^{k_1},\dots ,q_r^{k_r})$.

Let $n=(P^{\kappa }{)}^1=p_1^{k_1}\cdots p_r^{k_r}$. Then

$\begin{array}{cc}\prod _{j=1}^r(p_j^{k_j}-p_j^{k_j-1})& =\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{array}$.$◻$

Lemma 2.10:

$\phi =\mu *I_1$.

Proof 1:

We prove the lemma from lemma 2.14.

We have by lemma 2.14

$\begin{array}{cc}\phi (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{array}$$◻$

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}$

$\phi (n)=\prod _{j=1}^r(p_j^{k_j}-p_j^{k_j-1})=\mu *I_1$.$◻$

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$.$◻$

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.$◻$

Proof 3:

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

$\begin{array}{cc}E*\mu (n)& =\sum _{d|n}\mu (d)\\ & =\sum _{\alpha \in \{0,1{\}}^r}\mu (P^{\alpha })\\ & =\sum _{\beta \in \{0,1{\}}^{r-1}}(\mu (P^{(0,\beta )})+\mu (P^{(1,\beta )}))=0\end{array}$.$◻$

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\le r$, there exist $(\genfrac{}{}{0ex}{}{m}{r})$ distinct ways to pick a subset $I\subseteq \{1,\dots ,r\}$ such that $|I|=m$. Define ${\alpha }_I=({\alpha }_1,\dots ,{\alpha }_r)\in \{0,1{\}}^r$ where ${\alpha }_j=1\iff j\in I$. Then, by the Binomial theorem

$\begin{array}{cc}E*\mu (n)& =\sum _{d|n}\mu (d)\\ & =\sum _{I\subseteq \{1,\dots ,r\}}\mu (P^{{\alpha }_I})\\ & =\sum _{I\subseteq \{1,\dots ,r\}}(-1{)}^{|I|}\\ & =\sum _{j=0}^r(\genfrac{}{}{0ex}{}{j}{r})(-1{)}^j{1}^j=(1-1{)}^r=0\end{array}$.$◻$

Formulas for Euler's totient function

Lemma 2.11 (Gauß 1801):

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

$\phi (n)=\mu *I_1(n)$

by lemma 2.10.

Hence, we obtain $\mu *S_{\phi }=\mu *I_1$, and by cancellation of $\mu$ (the arithmetic functions form an integral domain) we get the lemma.$◻$

Proof 2:

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

Since $\phi (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_{\phi }(n)$.$◻$

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\le m\le n$.

We now prove that there are also $\sum _{d|n}\phi (d)$ many fractions of this form. Indeed, each fraction $\frac{m}{n}$, $1\le m\le 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 $\phi (d)$ many such fractions by definition of $\phi$.$◻$

Proof 4:

We prove the lemma by the means of set theory.

Define $S_{n,d}:=\{1\le l\le n|\gcd (d,l)=1\}$. Then $S_{n,d}=\{dk|1\le k\le n/d,\gcd (k,n)=1\}=d{S}_{n/d,1}$. Since $|S_{n/d,1}|=\phi (n/d)$ and $\{1,\dots ,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\phi \left(\frac{n}{d}\right)$.$◻$

The next theorem comprises one of the most important examples for a multiplicative function.

Proof 1:

We prove the theorem using double counting (due to Kronecker).

By definition of $\phi$, there are $\phi (m)\phi (n)$ sums of the form

$\frac{k}{m}+\frac{l}{n},1\le k\le m,1\le l\le n$,

where both summands are reduced. We claim that there is a bijection

$\{\frac{k}{m}+\frac{l}{n}|1\le k\le m,1\le l\le n,\frac{k}{m},\frac{l}{n}\text{ reduced}\}\to \left\{\frac{r}{mn}\right|1\le r\le \frac{r}{mn}\text{ reduced}\}$.

From this would follow $\phi (m)\phi (n)=\phi (mn)$.

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

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

$\frac{k}{m}+\frac{l}{n}=\frac{kn+lmmodmn}{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=ramodm$, $l=rbmodn$. Then

$kn+lm=(ra+tm)n+(rb+sn)m\equiv rmodmn$.

Injectivity: Let $kn+lm\equiv k^{\prime }n+l^{\prime }mmodmn$. We show $k=k^{\prime }$; the proof for $l=l^{\prime }$ is the same.

Indeed, from $kn+lm\equiv k^{\prime }n+l^{\prime }mmodmn$ follows $kn\equiv k^{\prime }nmodm$, 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^{\prime }modm$. Since $1\le k,k^{\prime }\le m$, the claim follows.$◻$

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 {(\mathbb{Z}/p_1^{k_1})}^{\times }\times \cdots \times {(\mathbb{Z}/p_r^{k_r})}^{\times }$.

Hence, $|(\mathbb{Z}/n{)}^{*}|=\prod _{j=1}^r\left|{(\mathbb{Z}/p_j^{k_j})}^{*}\right|$, and from $\mathrm{\forall }m\in \mathbb{N}:\phi (m)=|(\mathbb{Z}/m{)}^{*}|$ follows the claim.$◻$

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}\phi (e)$ and $n=\sum _{d|m}\phi (d)$ and hence

$mn=\phi (m)\phi (n)+\phi (m)\sum _{d|n,d<n}\phi (d)+\phi (n)\sum _{e|m,e<m}\phi (e)+\sum _{\genfrac{}{}{0ex}{}{d|n,e|m}{d<n,e<m}}\phi (d)\phi (e)$.

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

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

By induction on $ed,en,md<mn$ we thus have

$mn=\phi (mn)+\phi (m)\sum _{d|n}\phi (d)+\phi (n)\sum _{e|m}\phi (e)+\sum _{\genfrac{}{}{0ex}{}{e|m,d|n}{e<m,d<n}}\phi (e)\phi (d)$.$◻$

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

$\phi =\mu *I_1$,

which is why $\phi$ is multiplicative as the convolution of two multiplicative functions.$◻$

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=\mathrm{\varnothing }$ and hence

$\prod _{p|n}(p^{{\kappa }_p}-p^{{\kappa }_p-1})\prod _{q|n}(q^{\iota }-q^{{\iota }_q-1})=\phi (mn)$.$◻$

Proof:

By lemma 2.14 and associativity of convolution,

$\mu *S_f=\mu *f*E=\mu *E*f=\delta *f=f$.$◻$

Proof 1:

We prove the theorem from lemma 2.10 and the fact that $\phi$ is multiplicative.

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

$\phi (p^k)=(\mu *I_1)(p^k)=\sum _{j=0}^k\mu (p^j)p^{k-j}$

by lemma 2.10. Therefore,

$\phi (n)=\prod _{j=1}^r(p_j^{k_j}-p_j^{k_j-1})=n\prod _{j=1}^r$,

where the latter equation follows from

$\begin{array}{cc}n\prod _{j=1}^r(1-\frac{1}{p_j})& =p_1^{k_1}\cdots p_r^{k_r}\prod _{j=1}^r(1-\frac{1}{p_j})\\ & =\prod _{j=1}^r{p}_j^{k_j}(1-\frac{1}{p_j})\\ & =\prod _{j=1}^r(p_j^{k_j}-p_j^{k_j-1})\end{array}$.$◻$

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 $\mathrm{\Omega }=\{1,\dots ,n\}$, $ℱ=2^{\mathrm{\Omega }}$, $P(A):=\frac{|A|}{n}$. For $j\in \{1,\dots ,r\}$ define the event $E_{p_j}:=\{1\le k\le n|p_j|n\}$. Then we have

$P(\overline{E_{p_1}}\cap \cdots \cap \overline{E_{p_r}})=\frac{\phi (n)}{n}$.

On the other hand, for each $J=\{j_1,\dots ,j_l\}\subseteq \{1,\dots ,r\}$, we have

$\begin{array}{cc}P(E_{p_{j_1}}\cap \cdots \cap E_{p_{j_1}})& =P\left(\{1\le k\le n|\prod _{j\in J}{p}_j|k\}\right)\\ & =\frac{1}{\prod _{j\in J}{p}_j}=\prod _{j\in J}P\left(E_{p_j}\right)\end{array}$.

Thus, it follows that $E_{p_1},\dots ,E_{p_r}$ are independent. But since events are independent if and only if their complements are, we obtain

$\frac{\phi (n)}{n}=P(\overline{E_{p_1}}\cap \cdots \cap \overline{E_{p_r}})=P(\overline{E_{p_1}}))\cdots P\left(\overline{E_{p_r}}\right)=\prod _{j=1}^r(1-\frac{1}{p_j})$.$◻$

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_{\phi }=I_1$,

$\sum _{d|n}\mu (d)\frac{n}{d}=\mu *S_{\phi }(n)=\phi (n)$.$◻$

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,\dots ,A_r\subseteq S$

$\begin{array}{cc}\left|\bigcap _{j=1}^r{A}_j\right|& =|S\setminus \bigcup _{j=1}^r(S\setminus A_j)|\\ & =|S|-\left|\bigcup _{j=1}^r(S\setminus A_j)\right|\\ & =|S|+\sum _{\mathrm{\varnothing }\ne J\subseteq \{1,\dots ,r\}}(-1{)}^{|J|}\left|\bigcap _{j\in J}(S\setminus A_j)\right|\\ & =\sum _{J\subseteq \{1,\dots ,r\}}(-1{)}^{|J|}\left|\bigcap _{j\in J}(S\setminus A_j)\right|\end{array}$,

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\le m\le n\}$ and $A_j:=\{l\in S|p_j|l\}$ for $1\le j\le r$. Since

$\phi (n)=\left|\bigcap _{j=1}^r{A}_j\right|$,

we then have

$\phi (n)=\sum _{J\subseteq \{1,\dots ,r\}}(-1{)}^{|J|}\left|\bigcap _{j\in J}(S\setminus A_j)\right|$.

But for each $J\subseteq \{1,\dots ,r\}$, we have

$\begin{array}{cc}\left|\bigcap _{j\in J}(S\setminus A_j)\right|& =\{1\le l\le n|\mathrm{\forall }j\in J:p_j|l\}\\ & =\{1\le l\le n|\left(\prod _{j\in J}{p}_j\right)|l\}=\frac{n}{\prod _{j\in J}{p}_j}\end{array}$.

It follows

$\phi (n)=n\sum _{J\subseteq \{1,\dots ,r\}}(-1{)}^{|J|}\frac{1}{\prod _{j\in J}{p}_j}$,

and since

$\prod {m=1}^r(1-\frac{1}{p_m})=\sum _{J\subseteq \{1,\dots ,r\}}(-1{)}^{|J|}\frac{1}{\prod _{j\in J}{p}_j}$,

the theorem is proven.$◻$