Analytic Number Theory/Printable version

Analytic Number Theory

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Analytic_Number_Theory

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

Useful summation formulas

Analytic number theory is so abysmally complex that we need a basic toolkit of summation formulas first in order to prove some of the most basic theorems of the theory.

Abel's summation formula

Theorem 1.1 (Abel's summation formula, also called Abel's identity):

Let $(a_{n})_{n\in \mathbb {N} }$ be a sequence and let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function such that $f'$ is Riemann integrable. If we define

$A(x):=\sum _{1\leq n\leq x}a_{n}$,

then we have

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x)f(x)-\int _{1}^{x}A(y)f'(y)dy$.

Note: We need the Riemann integrability to be able to apply the fundamental theorem of calculus.

Proof 1:

We prove the theorem by induction on $\lfloor x\rfloor$.

1. $\lfloor x\rfloor =1$:

First, we have in this case

$\sum _{1\leq n\leq x}a_{n}f(n)=a_{1}f(1)$.

Then, we have

$A(x)f(x)=a_{1}f(x)=a_{1}f(1)-a_{1}(f(1)-f(x))=a_{1}f(1)+\int _{1}^{x}A(y)f'(y)dy$

by the fundamental theorem of calculus.

2. Induction step:

Define $N:=\lfloor x\rfloor$. We have

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)&=\sum _{1\leq n\leq x-1}a_{n}f(n)+a_{N}f(N)\\&=A(x-1)f(x-1)-\int _{1}^{x-1}A(y)f'(y)dy+a_{N}f(N)\end{aligned}}$

by the induction hypothesis. Further,

${\begin{aligned}-\int _{1}^{x-1}A(y)f'(y)dy&=-\int _{1}^{x}A(y)f'(y)dy+\int _{x-1}^{x}A(y)f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+\int _{x-1}^{N}A(y)f'(y)dy+\int _{N}^{x}A(y)f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+A(N-1)\int _{x-1}^{N}f'(y)dy+A(N)\int _{N}^{x}f'(y)dy\\&=-\int _{1}^{x}A(y)f'(y)dy+A(N-1)(f(N)-f(x-1))+A(N)(f(x)-f(N))\end{aligned}}$.

Putting things together, we obtain

$\sum _{1\leq n\leq x}a_{n}f(n)=A(x-1)f(x-1)-\int _{1}^{x}A(y)f'(y)dy+A(N-1)(f(N)-f(x-1))+A(N)(f(x)-f(N))+a_{N}f(N)$

and thus the desired formula.

The method of proof we applied here was using induction and then trying to express the terms from the induction hypothesis in terms of the terms from the desired formula.$\Box$

Proof 2:

We prove the theorem by direct manipulation of the term on the left.

Define $k:=\lfloor x\rfloor$.

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)&=\sum _{1\leq n\leq x}(A(n)-A(n-1))f(n)\\&=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{0\leq n\leq x-1}A(n)f(n+1)=\sum _{1\leq n\leq x}A(n)f(n)-\sum _{1\leq n\leq x-1}A(n)f(n+1)\\&=\sum _{1\leq n\leq x-1}A(n)(f(n)-f(n+1))+A(k)f(k)\\&=\sum _{1\leq n\leq x-1}A(n)\left(-\int _{n}^{n+1}f'(t)dt\right)+A(x)f(x)-\int _{k}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Proof 3:

We prove the formula by the means of the Riemann-Stieltjes integral. Indeed, by integration by parts, we have

${\begin{aligned}\sum _{1\leq n\leq x}a_{n}f(n)=\int _{0}^{x}f(t)dA(t)&=A(x)f(x)-\int _{0}^{x}A(t)df(t)\\&=A(x)f(x)-\int _{1}^{x}A(t)f'(t)dt\end{aligned}}$.$\Box$

Corollary 1.2:

$\sum _{y<n\leq x}a_{n}f(n)=A(x)f(x)-A(y)f(y)-\int _{y}^{x}A(t)f'(t)dt$.

Proof 1:

We deduce the formula from integration by parts for the Riemann-Stieltjes integral.

${\begin{aligned}\sum _{y<n\leq x}a_{n}f(n)=\int _{y}^{x}f(t)dA(t)&=f(x)A(x)-f(y)A(y)-\int _{y}^{x}A(t)df(t)\\&=f(x)A(x)-f(y)A(y)-\int _{y}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Proof 2:

We directly manipulate the LHS (left hand side).

Define $k:=\lfloor x\rfloor$ and $m:=\lfloor y\rfloor$.

${\begin{aligned}\sum _{y<n\leq x}a_{n}f(n)&=\sum _{y<n\leq x}(A(n)-A(n-1))f(n)\\&=\sum _{y<n\leq x}A(n)f(n)-\sum _{y-1<n\leq x-1}A(n)f(n+1)\\&=\sum _{y<n\leq x-1}A(n)(f(n)-f(n+1))-A(m)f(m)+A(k)f(k)\\&=\sum _{y<n\leq x-1}A(n)-\left(\int _{n}^{n+1}f'(t)dt\right)-A(y)f(y)+A(x)f(x)-\int _{y}^{m}A(t)f'(t)dt-\int _{k}^{x}A(t)f'(t)dt\end{aligned}}$$\Box$

Two further proofs are given in exercises 1.1.1 and 1.1.5.

We note that induction and direct manipulation are quicker proofs for theorem 1.1, while corollary 1.2 is quicker proven from theorem 1.1 or Riemann-Stieltjes integration.

Exercises

• Exercise 1.1.1: Prove corollary 1.2 from theorem 1.1. Hint: $\sum _{y<n\leq x}a_{n}f(n)=\sum _{1\leq n\leq x}a_{n}f(n)-\sum _{1<n\leq y}a_{n}f(n)$.
• Exercise 1.1.2: Compute $\sum _{n=1}^{N}n^{3}$. Hint: Use $a_{n}=n$, $f(x)=x^{2}$, apply Abelian summation and split the resulting integral into pieces where $A(t)$ is constant. Then apply a similar process.
• Exercise 1.1.3: Prove that the limit $\lim _{n\to \infty }\left(-\log(n)+\sum _{k=1}^{n}{\frac {1}{k}}\right)$ exists. This limit is called the Euler–Mascheroni constant. Hint: Use $a_{n}=1$ and $f(x)={\frac {1}{x}}$.
• Exercise 1.1.4: Prove theorem 1.1 from corollary 1.2.
• Exercise 1.1.5: Prove corollary 1.2 using induction on $\lfloor x\rfloor$.

Euler's summation formula

Definition 1.3:

For $x\in \mathbb {R}$, we define

$\{x\}:=x-\lfloor x\rfloor$.

Theorem 1.4 (Euler's summation formula):

Let $f:\mathbb {R} \to \mathbb {R}$ be a differentiable function, such that $f'$ is Riemann integrable. Then

$\sum _{y<n\leq x}f(n)=\{x\}f(x)-\{y\}f(y)+\int _{y}^{x}f(t)dt+\int _{y}^{x}\{t\}f'(t)dt$.

Proof:

We prove the theorem from Corollary 1.2, setting $a_{n}=1$ and using integration by parts (integration by parts is proven using the fundamental theorem of calculus).

Indeed,

${\begin{aligned}\sum _{y<n\leq x}f(n)&=\lfloor x\rfloor f(x)-\lfloor y\rfloor f(y)-\int _{y}^{x}\lfloor t\rfloor f'(t)dt\\&=\lfloor x\rfloor f(x)-\lfloor y\rfloor f(y)-\int _{y}^{x}tf'(t)dt+\int _{y}^{x}\{t\}f'(t)dt\\&=\{x\}f(x)-\{y\}f(y)+\int _{y}^{x}f(t)dt+\int _{y}^{x}\{t\}f'(t)dt\end{aligned}}$,

where in the last line we used integration by parts on the integral $\int _{y}^{x}tf'(t)dt$.$\Box$

Corollary 1.5:

Exercises

1. Prove corollary 1.5.

Euler–Maclaurin formula

Theorem 1.6 (Euler–Maclaurin formula):

Define the functions $\rho (x):={\frac {1}{2}}-x$ and $\sigma (x):=\int _{0}^{x}\rho (y)dy$. Then for any twice continuously differentiable function $f$ such that $f''$ is Riemann integrable, we have

$\sum _{y<n\leq x}f(n)=\int _{x}^{y}f(t)dt+\rho (y)f(y)-\rho (x)f(x)+\sigma (x)f'(x)-\sigma (y)f'(y)+\int _{x}^{y}\sigma (t)f''(t)dt$.

Proof 1:

We prove the theorem by direct computation.

${\begin{aligned}\end{aligned}}$

Proof 2:

We prove the theorem from Euler's summation formula.

The Chebychev ψ and ϑ functions

Proposition (the Chebychev ψ function may be written as the sum of Chebyshev ϑ functions):

We have the identity

$\psi (x)=\sum _{m=1}^{\log _{2}(x)}\vartheta (x^{1/m})$.

Proposition (estimate of the distance between the Chebychev ψ and ϑ functions):

Whenever $x\geq 3,594,641$, we have

$\psi (x)-\vartheta (x)={\sqrt {x}}+O\left({\frac {\sqrt {x}}{\ln(x)^{2}}}\right)$.

Note: The current proof gives an inferior error term. A subsequent version will redeem this issue. (Given the Riemann hypothesis, the error term can be made even smaller.)

Proof: We know that the formula

$\psi (x)=\sum _{m=1}^{\log _{2}(x)}\vartheta (x^{1/m})$

holds. Hence,

$\psi (x)-\vartheta (x)=\sum _{m=2}^{\log _{2}(x)}\vartheta (x^{1/m})$.

By a result obtained by Pierre Dusart (based upon the computational verification of the Riemann hypothesis for small moduli), we have

$\left|\theta (x)-x\right|\leq {\frac {0.2}{\ln(x)^{2}}}x$

whenever $x\geq 3,594,641$. If $x$ is in that range, we hence conclude

$\psi (x)-\vartheta (x)=\sum _{m=2}^{\log _{2}(x)}\vartheta (x^{1/m})\leq \left(1+{\frac {0.2}{\ln(x)^{2}}}\right)\sum _{m=2}^{\log _{2}(x)}x^{1/m}$.

By Euler's summation formula, we have

$\sum _{m=2}^{\log _{2}(x)}x^{1/m}=\int _{2}^{\log _{2}(x)}x^{1/t}dt+\int _{2}^{\log _{2}(x)}\{t\}\left({\frac {d}{dt}}x^{1/t}\right)dt+\{\log _{2}(x)\}x^{1/\log _{2}(x)}-\{2\}x^{1/2}$.

Certainly $\{2\}=0$ and $\{\log _{2}(x)\}\leq 1$. Moreover, $x^{1/\log _{2}(x)}=2$. Now derivation shows that

$-\exp \left({\frac {\ln(x)}{t}}\right){\frac {t^{2}}{\ln(x)}}$

is an anti-derivative of the function

$x^{1/t}-{\frac {2t}{\ln(x)}}x^{1/t}$

of $t$. By the fundamental theorem of calculus, it follows that

$\int _{a}^{b}\left(1-{\frac {2t}{\ln(x)}}\right)x^{1/t}dt=\left[-\exp \left({\frac {\ln(x)}{t}}\right){\frac {t^{2}}{\ln(x)}}\right]_{t=a}^{t=b}$

for real numbers $a,b\in \mathbb {R}$ such that $a<b$. This integral is not precisely the one we want to estimate. Hence, some analytical trickery will be necessary in order to obtain the estimate we want.

We start by noting that if only the bracketed term in the integral were absent, we would have the estimate we desire. In order to proceed, we replace $x$ by the more general expression $xy$ (where $y\geq 1$), and obtain

$\int _{a}^{b}\left(1-{\frac {2t}{\ln(xy)}}\right)x^{1/t}y^{1/t}dt=\left[-\exp \left({\frac {\ln(xy)}{t}}\right){\frac {t^{2}}{\ln(xy)}}\right]_{t=a}^{t=b}$.

The integrand is non-negative so long as

$t\leq {\frac {\ln(xy)}{2}}$.

Moreover, if $t_{0}$ is strictly within that range, we obtain

$\int _{2}^{t_{0}}x^{1/t}y^{1/t}dt\leq \left(1-{\frac {2t_{0}}{\ln(xy)}}\right)^{-1}\int _{2}^{t_{0}}\left(1-{\frac {2t}{\ln(xy)}}\right)x^{1/t}y^{1/t}dt=\left[-\exp \left({\frac {\ln(xy)}{t}}\right){\frac {t^{2}}{\ln(xy)}}\right]_{t=2}^{t=t_{0}}$.

We now introduce a constant $K\in (2,t_{0})$ and obtain the integrals

$\int _{2}^{K}x^{1/t}y^{1/t}dt$ and $\int _{K}^{t_{0}}x^{1/t}y^{1/t}dt$.

The first integral majorises the integral

$y^{1/K}\int _{2}^{K}x^{1/t}dt$,

whereas the second integral majorises the integral

$\int _{K}^{t_{0}}x^{1/t}dt$.

We obtain that

$\int _{2}^{t_{0}}x^{1/t}dt\leq {\frac {1}{y^{1/K}}}\int _{2}^{K}x^{1/t}y_{1}^{1/t}dt+\int _{K}^{t_{0}}x^{1/t}y_{2}^{1/t}dt$.

Now we would like to set $t_{0}=\log _{2}(x)$. To do so, we must ensure that $y$ is sufficiently large so that $K$ resp. $t_{0}$ is strictly within the admissible interval.

The two summands on the left are now estimated using our computation above, where $t_{0}$ is replaced by $K$ for the first computation: Indeed,

$\int _{2}^{K}x^{1/t}y_{1}^{1/t}dt\leq \left(1-{\frac {2K}{\ln(xy_{1})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}$

and

$\int _{K}^{t_{0}}x^{1/t}y_{2}^{1/t}dt\leq \left(1-{\frac {2t_{0}}{\ln(xy_{2})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{2})}{t}}\right){\frac {t^{2}}{\ln(xy_{2})}}\right]_{t=K}^{t=t_{0}}$.

Putting the estimates together and setting $t_{0}=\log _{2}(x)$, we obtain

$\int _{2}^{\log _{2}(x)}x^{1/t}dt\leq {\frac {1}{y_{1}^{1/K}}}\left(1-{\frac {2K}{\ln(xy_{1})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}+\left(1-{\frac {2t_{0}}{\ln(xy_{2})}}\right)^{-1}\left[-\exp \left({\frac {\ln(xy_{2})}{t}}\right){\frac {t^{2}}{\ln(xy_{2})}}\right]_{t=K}^{t=\log _{2}(x)}$

whenever

$K\leq {\frac {\ln(xy_{1})}{2}}$ and $\log _{2}(x)\leq {\frac {\ln(xy_{2})}{2}}$.

We now choose the ansatz

$1-{\frac {2K}{\ln(xy_{1})}}=C$ and $1-{\frac {2t_{0}}{\ln(xy_{2})}}=D$

for constants $C$ and $D$. These equations are readily seen to imply

$y_{1}={\frac {1}{x}}\exp \left({\frac {2K}{1-C}}\right)$ and $y_{2}={\frac {1}{x}}\exp \left({\frac {2\log _{2}(x)}{1-D}}\right)$.

Note though that $y_{1}\geq 1$ and $y_{2}\geq 1$ is needed. The first condition yields

$K\geq {\frac {1-C}{2}}\ln(x)$.

The equations for $y_{1}$ and $y_{2}$ may be inserted into the above constraints on $K$ and $\log _{2}(x)$; this yields

$K\leq {\frac {2K}{1-C}}$ and $\log _{2}(x)\leq {\frac {2\log _{2}(x)}{1-D}}$, that is, $C\geq {\frac {1}{2}}$ and $D\geq {\frac {1}{2}}$.

If all these conditions are true, the ansatz immediately yields

$\int _{2}^{\log _{2}(x)}x^{1/t}dt\leq {\frac {C^{-1}}{y_{1}^{1/K}}}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}+D^{-1}\left[-\exp \left({\frac {\ln(xy_{2})}{t}}\right){\frac {t^{2}}{\ln(xy_{2})}}\right]_{t=K}^{t=\log _{2}(x)}$.

We now amend our ansatz by further postulating

$K=\left({\frac {1-C}{2}}+\alpha \right)\ln(x)$.

This yields

$y_{1}={\frac {1}{x}}\exp \left({\frac {(1-C+2\alpha )\ln(x)}{1-C}}\right)$

and

${\frac {C^{-1}}{y_{1}^{1/K}}}\left[-\exp \left({\frac {\ln(xy_{1})}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}={\frac {C^{-1}}{y_{1}^{1/K}}}\left[-\exp \left({\frac {\frac {(1-C+2\alpha )\ln(x)}{1-C}}{t}}\right){\frac {t^{2}}{\ln(xy_{1})}}\right]_{t=2}^{t=K}$.

From this we deduce that in order to obtain an asymptotically sharp error term, we need to set $\alpha =0$. But doing so yields the desired result. $\Box$

Arithmetic functions

In this chapter, we shall set up the basic theory of arithmetic functions. This theory will be seen in action in later chapters, but in particular in chapter 9.

Definitions

Definition 2.1:

An arithmetical function is a function $f:\mathbb {N} \to \mathbb {C}$.

Definition 2.2 (important arithmetical functions):

1. The Kronecker delta: $\delta (n):={\begin{cases}1&n=1\\0&n\neq 1\end{cases}}$
2. Euler's totient function: $\varphi (n):=\left|\{1\leq k\leq n|\gcd(k,n)=1\}\right|$
3. Möbius' $\mu$-function: $\mu (n):={\begin{cases}0&{\text{ there exists }}m\in \mathbb {N} {\text{ such that }}m^{2}|n\\(-1)^{r}&n{\text{ is product of }}r{\text{ pairwise different prime numbers}}\\1&n=1\end{cases}}$
4. The von Mangoldt function: $\Lambda (n):={\begin{cases}\log(p)&\exists p{\text{ prime}},k\in \mathbb {N} :n=p^{k}\\0&{\text{otherwise}}\end{cases}}$
5. The monomials: $I_{k}(n):=n^{k}$
6. The number of distinct prime divisors: $\omega (n):=r,n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, $k_{1},\ldots ,k_{r}\in \mathbb {N}$
7. The sum of prime factors with multiplicity: $\Omega (n):=k_{1}+\cdots +k_{r},n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, $k_{1},\ldots ,k_{r}\in \mathbb {N}$
8. The Liouville function: $\lambda (n):=(-1)^{\Omega (n)}$

Exercises

• Exercise 2.1.1: Compute $\varphi (20)$, $\varphi (17)$ and $\varphi (22)$.
• Exercise 2.1.2: Compute $\mu (4278)$. Hint: $4278=2\cdot 3\cdot 23\cdot 31$.
• Exercise 2.1.3: Compute $\Lambda (49)$ up to three decimal places. Hint: Use a Taylor expansion.
• Exercise 2.1.4: Prove that for each $n\in \mathbb {N}$ and $k_{1},k_{2},k_{3},k_{4}\in \mathbb {N}$ $\mu (n+4k_{1})\mu (n+4k_{2}+1)\mu (n+4k_{3}+2)\mu (n+4k_{4}+3)=0$.

The convolution and the ring of arithmetic functions

Definition 2.3:

Let $f,g:\mathbb {N} \to \mathbb {C}$ be arithmetical functions. Then the convolution of $f$ and $g$ is defined to be the function

$f*g(n):=\sum _{d|n}f(d)g\left({\frac {n}{d}}\right)$.

In the following theorem, we show that the arithmetical functions form an Abelian monoid, where the monoid operation is given by the convolution. Further, since the sum of two arithmetic functions is again an arithmetic function, the arithmetic functions form a commutative ring. In fact, as we shall also see, they form an integral domain.

Theorem 2.4 (Abelian monoid properties of the arithmetical functions):

1. The convolution is commutative, i. e. $f*g=g*f$.
2. The convolution is associative, i. e. $f*(g*h)=(f*g)*h$.
3. The function $\delta$ from definition 2.2 is an identity for the convolution, i. e. $\delta *f=f$.

Proof:

1.:

${\begin{aligned}f*g(n)&=\sum _{d|n}f(d)g\left({\frac {n}{d}}\right)=\sum _{d|n}f(\psi (d))g\left(\psi \left({\frac {n}{d}}\right)\right)\\&=\sum _{d|n}f\left({\frac {n}{d}}\right)g(d)=g*f(n)\end{aligned}}$,

where $\psi (d):={\frac {n}{d}}$ is a bijection from the set of divisors of $n$ to itself.

2.:

${\begin{aligned}f*(g*h)=f*(h*g)&=\sum _{d_{1}|n}f(d_{1})\left(\sum _{d_{2}|{\frac {n}{d_{1}}}}g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})\right)\\&=\sum _{d_{1}|n}\sum _{d_{2}|{\frac {n}{d_{1}}}}f(d_{1})g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})\\&=\sum _{d_{2}|n}\sum _{d_{1}|{\frac {n}{d_{2}}}}f(d_{1})g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})\end{aligned}}$,

where the last equality follows from the identity function

$Id:\left\{(d_{1},d_{2}):d_{2}|n,d_{1}{\big |}{\frac {n}{d_{2}}}\right\}\to \left\{(d_{1},d_{2}):d_{1}|n,d_{2}{\big |}{\frac {n}{d_{1}}}\right\}$

being a bijection. But

$\sum _{d_{2}|n}\sum _{d_{1}|{\frac {n}{d_{2}}}}f(d_{1})g\left({\frac {n}{d_{1}d_{2}}}\right)h(d_{2})=(f*g)*h$

and hence associativity.

3.:

$\delta *f(n)=\sum _{d|n}\delta (d)f\left({\frac {n}{d}}\right)=f(n)$$\Box$

Theorem 2.5:

The ring of arithmetic functions is an integral domain.

Proof: Let $f,g\neq 0$ be arithmetic functions, and let $n,k\in \mathbb {N}$ be minimal such that $f(n)\neq 0$, $g(k)\neq 0$. Then

$f*g(nk)=\sum _{d|nk}f(d)g\left({\frac {nk}{d}}\right)=f(n)g(k)$.$\Box$

We shall now determine the units of the ring of arithmetic functions.

Theorem 2.6:

Let $f$ be an arithmetic function. Then $f$ is invertible (with respect to convolution) if and only if $f(1)\neq 0$.

Proof:

Assume first $f(1)=0$. Then for any arithmetic function $g$, $f*g(1)=0\neq 1=\delta (1)$.

Assume now $f(1)\neq 0$. Then $g$, given by the recursive formula

$g(1)=f(1)^{-1}$,

$g(n)=-f(1)^{-1}\sum _{d|n \atop d<n}g(d)f\left({\frac {n}{d}}\right)=g(n)-f(1)^{-1}g*f(n)$, $n>1$

is an inverse (and thus the inverse) of $f$, since $f*g(1)=f(1)g(1)=1$ and for $n>1$ inductively

${\begin{aligned}f*g(n)&=f*g(n)-f(1)^{-1}f*g*f(n)\\&=f*g(n)-f^{-1}\sum _{d|n \atop d<n}f*g(d)f\left({\frac {n}{d}}\right)=0\end{aligned}}$

$\Box$

Exercises

• Exercise 2.2.1:
• Exercise 2.2.2:

Multiplicative functions

Definition 2.7:

An arithmetical function $f:\mathbb {N} \to \mathbb {C}$ is called multiplicative iff it satisfies

1. $\forall n,k\in \mathbb {N} :\gcd(n,k)=1\Rightarrow f(nk)=f(n)f(k)$, and
2. $f(1)=1$.

Theorem 2.8:

Let $f,g$ be multiplicative arithmetical functions. Then $f*g$ is multiplicative.

Proof:

Let $\gcd(k,n)=1$. Then

$f*g(kn)=\sum _{d|(kn)}f(d)g\left({\frac {kn}{d}}\right)=\sum _{d_{1}|k \atop d_{2}|n}f(d_{1}d_{2})g\left({\frac {kn}{d_{1}d_{2}}}\right)$,

since the function $\theta (d):=(\gcd(d,n),\gcd(d,k))$ is a bijection from the divisors of $nk$ to the Cartesian product of the divisors of $n$ and the divisors of $k$; this is because multiplication is the inverse:

$\gcd(d,n)\gcd(d,k)=d$, $(\gcd(d_{1}d_{2},n),\gcd(d_{1}d_{2},k))=(d_{1},d_{2})$.

To rigorously prove this actually is an exercise in itself. But due to the multiplicativity of $f$ and $g$,

$\sum _{d_{1}|k \atop d_{2}|n}f(d_{1}d_{2})g\left({\frac {kn}{d_{1}d_{2}}}\right)=\sum _{d_{1}|k \atop d_{2}|n}f(d_{1})g\left({\frac {k}{d_{1}}}\right)f(d_{2})g\left({\frac {n}{d_{2}}}\right)=f*g(k)\cdot f*g(n)$.

Furthermore, $f*g(1)=f(1)g(1)=1$.$\Box$

Since $\delta$ is multiplicative, we conclude that the multiplicative functions form an Abelian submonoid of the arithmetic functions with convolution. Unfortunately, we do not have a subring since the sum of two multiplicative functions is never multiplicative (look at $n=1$).

Theorem 2.9:

Let $f$ be a multiplicative function such that $\sum _{j=1}^{\infty }f(j)$ converges absolutely. Then

$\sum _{j=1}^{\infty }f(j)=\prod _{p{\text{ prime}}}\left(\sum _{k=0}^{\infty }f(p^{k})\right)$.

Proof: Let $p_{1},p_{2},p_{3},\ldots =2,3,5,\ldots$ be the ordered sequence of all prime numbers. For all $m_{1},\ldots ,m_{r},r\in \mathbb {N}$ we have

$S_{f,r,m_{1},\ldots ,m_{r}}:=\sum _{d|\left(p_{1}^{m_{1}}\cdots p_{r}^{m_{r}}\right)}f(d)=\sum _{0\leq k_{1}\leq m_{1}}\cdots \sum _{0\leq k_{r}\leq m_{r}}f\left(p_{1}^{k_{1}}\right)\cdots f\left(p_{r}^{k_{r}}\right)=\prod _{l=1}^{r}\left(\sum _{k=0}^{m_{l}}f(p_{l}^{k})\right)$

due to the multiplicativity of $f$. For each $r$, we successively take $m_{1}\to \infty$, ..., $m_{r}\to \infty$ and then $r\to \infty$. It follows from the definitions and the rule $x_{n}\to x\Rightarrow yx_{n}\to yx$ that the right hand side converges to

$\prod _{l=1}^{\infty }\left(\sum _{k=0}^{\infty }f(p_{l}^{k})\right)$.

We claim that

$\lim _{r\to \infty }\lim _{m_{1}\to \infty }\cdots \lim _{m_{r}\to \infty }S_{f,r,m_{1},\ldots ,m_{r}}=\sum _{j=1}^{\infty }f(j)$.

Indeed, choose $N\in \mathbb {N}$ such that

$\sum _{j=N+1}^{\infty }|f(j)|<\epsilon$.

Then by the fundamental theorem of arithmetic, there exists an $R\in \mathbb {N}$ and $M_{1},\ldots ,M_{R}\in \mathbb {N}$ such that

$\forall j\in \{1,\ldots ,N\}:j|p_{1}^{M_{1}}\cdots p_{R}^{M_{R}}$.

Then we have by the triangle inequality for $T>R$, $L_{1}>M_{1},\ldots ,L_{R}>M_{R}$ and $L_{R+1},\ldots ,L_{T}$ arbitrary that

${\begin{aligned}\left|S_{f,T,L_{1},\ldots ,L_{T}}-\sum _{j=1}^{\infty }f(j)\right|&\leq \left|\sum _{d|\left(p_{1}^{L_{1}}\cdots p_{T}^{L_{T}}\right) \atop d\leq N}f(d)-\sum _{j=1}^{N}f(j)\right|+\left|\sum _{d|\left(p_{1}^{L_{1}}\cdots p_{T}^{L_{T}}\right) \atop d>N}f(d)-\sum _{j=N+1}^{\infty }f(j)\right|\\&<0+\epsilon .\end{aligned}}$

From this easily follows the claim.

It is left to show that the product on the left is independent of the order of multiplication. But this is clear since if the sequence $(p_{n})_{n\in \mathbb {N} }$ is enumerated differently, the argument works in just the same way and the left hand side remains the same.$\Box$

Definition 2.10:

An arithmetical function $f:\mathbb {N} \to \mathbb {C}$ is called strongly multiplicative iff it satisfies

1. $\forall n,k\in \mathbb {N} :f(nk)=f(n)f(k)$, and
2. $f(1)=1$.

Equivalently, a strongly multiplicative function is a monoid homomorphism $\mathbb {N} \to \mathbb {C} ^{\times }$.

Theorem 2.11:

Let $f$ be a strongly multiplicative function such that $\sum _{j=1}^{\infty }f(j)$ converges absolutely. Then

$\sum _{j=1}^{\infty }f(j)=\prod _{p{\text{ prime}}}{\frac {1}{1-f(p)}}$.

Proof:

Due to theorem 2.9, we have

$\sum _{n=1}^{\infty }f(n)=\prod _{p{\text{ prime}}}\left(\sum _{k=0}^{\infty }f(p^{k})\right)$.

Due to strong multiplicativity and the geometric series, the latter expression equals

$\prod _{p{\text{ prime}}}{\frac {1}{1-f(p)}}$.$\Box$

Exercises

• Exercise 2.3.1: Let $h$ be an arithmetic function such that for all $m,n\in \mathbb {N}$ $h(nm)=h(n)+h(m)$, and let $s\in \mathbb {C} \setminus \{0\}$. Prove that the function $f(n):=\exp(\log(s)h(n))$ is multiplicative.

Bell series

Definition 2.12:

Let $f$ be an arithmetic function. Then for a prime $p$ the Bell series modulo $p$ is the formal power series

$f_{p}(x):=\sum _{j=0}^{\infty }f(p^{j})x^{j}$.

Examples 2.13:

We shall here compute the Bell series for some important arithmetic functions.

We note that in general for a completely multiplicative function $f$, we have

$f_{p}(x)=\sum _{j=0}^{\infty }f(p)^{j}x^{j}={\frac {1}{1-f(p)x}}$.

In particular, in this case the Bell series defines a function.

1. The Kronecker delta:

$\delta _{p}(x)=\sum _{j=0}^{\infty }\delta (p^{j})x^{j}=1$

2. Euler' totient function (we use lemma 9.?):

${\begin{aligned}\varphi _{p}(x)&=\sum _{j=0}^{\infty }\varphi (p^{j})x^{j}\\&=\sum _{j=0}^{\infty }\varphi (p^{j})x^{j}\\&=1+\sum _{j=1}^{\infty }(p^{j}-p^{j-1})x^{j}\\&={\frac {1+x}{1-px}}\end{aligned}}$

3. The Möbius $mu$ function:

$\mu _{p}(x)=\sum _{j=0}^{\infty }\mu (p^{j})x^{j}=1-x$

4. The von Mangoldt function:

$\Lambda _{p}(x)=\sum _{j=0}^{\infty }\Lambda (p^{j})x^{j}=\sum _{j=0}^{\infty }\log(p)x^{j}$

5. The monomials:

$(I_{k})_{p}=\sum _{j=0}^{\infty }p^{kj}xj={\frac {1}{1-p^{k}x}}$

6. The number of distinct prime divisors:

$\omega _{p}(x)=\sum _{j=1}^{\infty }x^{j}={\frac {1}{1-x}}-1$

7. The number of prime divisors including multiplicity:

${\begin{aligned}\Omega _{p}(x)&=\sum _{j=1}^{\infty }jx^{j}\\&={\frac {1}{x}}\sum _{j=0}^{\infty }(x^{j})'\\&={\frac {1}{x}}\left(\sum _{j=0}^{\infty }x^{j}\right)'\\&={\frac {1}{x}}\left({\frac {1}{1-x}}\right)'\\&=-{\frac {1}{x}}{\frac {1}{(1-x)^{2}}}\end{aligned}}$

8. The Liouville function:

$\lambda _{p}(x)=\sum _{j=0}^{\infty }(-1)^{j}x^{j}={\frac {1}{1+x}}$

Theorem 2.14 (compatibility of Bell series and convolution):

Let $f,g$ arithmetic functions, and $p$ be a prime. Then

$f_{p}\cdot g_{p}=(f*g)_{p}$.

Proof:

${\begin{aligned}f_{p}(x)g_{p}(x)&=\left(\sum _{j=0}^{\infty }f(p^{j})x^{j}\right)\left(\sum _{j=0}^{\infty }g(p^{j})x^{j}\right)\\&=\sum _{k=0}^{\infty }x^{k}\left(\sum _{j=0}^{k}f(p^{j})g(p^{k-j})\right)\\&=\sum _{k=0}^{\infty }x^{k}(f*g)(p^{k})\end{aligned}}$$\Box$

In case of multiplicativity, we have the following theorem:

Theorem 2.15 (Uniqueness theorem):

Let $f,g$ be multiplicative functions. Then

$f=g\Leftrightarrow f_{p}=g_{p}$.

Proof: $\Rightarrow$ is pretty obvious; $\Leftarrow$: $f_{p}(x)=g_{p}(x)$ as formal power series is equivalent to saying $\forall k\in \mathbb {N} :f(p^{k})=g(p^{k})$. If now $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$, then

$f(n)=f(p_{1}^{k_{1}}\cdots p_{r}^{k_{r}})=f(p_{1}^{k_{1}})\cdots f(p_{r}^{k_{r}})=g(p_{1}^{k_{1}})\cdots g(p_{r}^{k_{r}})=g(n)$

due to the multiplicativity of $f$ and $g$.$\Box$

In chapter 9, we will use Bell series to obtain equations for number-theoretic functions.

Derivatives

Definition 2.16:

Let $f$ be an arithmetic function. Then the derivative of $f$ is defined to be the function

$f'(n):=f(n)\log(n)$.

Theorem 2.17 (rules for the derivative):

Let $f,g$ arithmetic functions. We have the following rules:

1. $(f+g)'=f'+g'$
2. $(f*g)'=f'*g+f*g'$
3. $(f^{-1})'=-f'\cdot (f*f)^{-1}$ if $f$ invertible, i.e.$f(1)\neq 0$

Note that $f^{-1}$ is not the inverse function of $f$ (this wouldn't make much sense anyway since $f$ arithmetic can not be surjective, since $\mathbb {C}$ is uncountable), but rather the convolution inverse.

Proof:

1. is easily checked.

2.:

${\begin{aligned}(f*g)'(n)&=(f*g)(n)\log(n)\\&=\sum _{d|n}f(d)g(n/d)(\log(d)+\log(n/d))\\&=\sum _{d|n}f(d)g(n/d)\log(d)+\sum _{d|n}f(d)g(n/d)\log(n/d)\end{aligned}}$

3.

We have $\delta '=0$ and $(f*f^{-1})=\delta$. Hence, by 2.

$0=(f*f^{-1})'=f'*f^{-1}+f*(f^{-1})'$.

Convolving with $f^{-1}$ and using $f^{-1}*f^{-1}=(f*f)^{-1}$ yields the desired formula.$\Box$

Note that a chain rule wouldn't make much sense, since $f$ arithmetic may map anywhere but to $\mathbb {N}$ and thus $g\circ f$ doesn't make a lot of sense in general.

Further reading

• terrytao.wordpress.com: Derived multiplicative functions

Characters and Dirichlet characters

Definitions, basic properties

Definition 4.1

Let $G$ be a finite group. A character of G is a function $f:G\to \mathbb {C}$ such that

1. $\forall \sigma ,\tau \in G:f(\sigma \tau )=f(\sigma )f(\tau )$ and
2. $\exists \rho \in G:f(\rho )\neq 0$.

Lemma 4.2:

Let $G$ be a finite group and let $f:G\to \mathbb {C}$ be a character. Then

$\forall \sigma \in G:|f(\sigma )|=1$.

In particular, $\forall \sigma \in G:f(\sigma )\neq 0$.

Proof:

Since $G$ is finite, each $\sigma \in G$ has finite order $n:=\mathrm {ord} (\sigma )$. Furthermore, let $\rho \in G$ such that $f(\rho )\neq 0$; then $f(\rho )=f(\sigma )f(\sigma ^{-1}\rho )$ and thus $f(\sigma )\neq 0$. Hence, we are allowed to cancel and

$|f(\sigma )|=|f(\sigma ^{n+1})|=|f(\sigma )|^{n+1}\Rightarrow |f(\sigma )|=1$.$\Box$

Lemma 4.3:

Let $G$ be a finite group and let $f,g:G\to \mathbb {C}$ be characters. Then the function $h:G\to \mathbb {C} ,h(\tau ):=f(\tau )\cdot g(\tau )$ is also a character.

Proof:

$h(\sigma \tau )=f(\sigma \tau )g(\sigma \tau )=f(\sigma )g(\sigma )f(\tau )g(\tau )=h(\sigma )h(\tau )\neq 0$,

since $\mathbb {C}$ is a field and thus free of zero divisors.$\Box$

Lemma 4.4:

Let $G$ be a finite group and let $f:G\to \mathbb {C}$ be a character. Then the function $g:G\to \mathbb {C} ,g(\tau ):={\frac {1}{f(\tau )}}$ is also a character.

Proof: Trivial, since $\forall \tau \in G:f(\tau )\neq 0$ as shown by the previous lemma.$\Box$

The previous three lemmas (or only the first, together with a few lemmas from elementary group theory) justify the following definition.

Definition 4.5

Let $G$ be a finite group. Then the group

$\{f:G\to \mathbb {C} |f{\text{ is a character }}\}=\mathrm {Hom} (G,\mathbb {C} ^{\times })$

is called the character group of $G$.

Required algebra

We need the following result from group theory:

Lemma 4.6

Let $G$ be a finite Abelian group, let $H\leq G$ be a subgroup of order $n\in \mathbb {N}$, and let $\tau \in G\setminus H$ such that $k\in \mathbb {N}$ is the smallest number such that $\tau ^{k}\in H$. Then the group

$N:=\{\tau ^{n}\sigma |\sigma \in H\}$

is a subgroup of $G$ containing $H$ of order $k\cdot n$.

Proof:

Since $G$ is the disjoint union of the cosets of $H$, $N$ is the disjoint union $\bigcup _{j=0}^{n-1}\tau ^{j}H$, as $\rho H=H\Leftrightarrow \rho \in H$ and $\tau ^{l}H=\tau ^{m}H\Leftrightarrow \tau ^{l-m}\in H\Leftrightarrow k|(l-m)$. Hence, the cardinality of $N$ equals $k\cdot n$.

Furthermore, if $\tau ^{l}\sigma ,\tau ^{m}\rho \in N$, then $\tau ^{l}\sigma (\tau ^{m}\rho )^{-1}=\tau ^{l-m}\sigma \rho ^{-1}\in N$, and hence $N$ is a subgroup.$\Box$

Dirichlet series

For the remainder of this book, we shall use Riemann's convention of denoting complex numbers:

$s=\sigma +it$

Definition

Definition 5.1:

Let $f$ be an arithmetic function. Then the Dirichlet series associated to $f$ is the series

$\sum _{n=1}^{\infty }{\frac {f(n)}{n^{s}}}$,

where $s$ ranges over the complex numbers.

Convergence considerations

Theorem 5.2 (abscissa of absolute convergence):

Let $f$ be an arithmetic function such that the series of absolute values associated to the Dirichlet series associated to $f$

$\sum _{n=1}^{\infty }\left|{\frac {f(n)}{n^{s}}}\right|$

neither diverges at all $s\in \mathbb {C}$ nor converges for all $s\in \mathbb {C}$. Then there exists $\sigma _{a}\in \mathbb {R}$, called the abscissa of absolute convergence, such that the Dirichlet series associated to $f$ converges absolutely for all $\sigma +it$, $\sigma >\sigma _{a}$ and it's associated series of absolute values diverges for all $\sigma +it$, $\sigma <\sigma _{a}$.

Proof:

Denote by $S$ the set of all real numbers $\sigma$ such that

$\sum _{n=1}^{\infty }\left|{\frac {f(n)}{n^{s}}}\right|$

diverges. Due to the assumption, this set is neither empty nor equal to $\mathbb {C}$. Further, if $\sigma _{0}+it_{0}\notin S$, then for all $\sigma >\sigma _{0}$ and all $t$ $\sigma +it\notin S$, since

$\left|{\frac {f(n)}{n^{s_{0}}}}\right|={\frac {|f(n)|}{n^{\sigma _{0}}}}\geq {\frac {|f(n)|}{n^{\sigma }}}=\left|{\frac {f(n)}{n^{s}}}\right|$

and due to the comparison test. It follows that $S$ has a supremum. Let $\sigma _{a}$ be that supremum. By definition, for $\sigma >\sigma _{a}$ we have convergence, and if we had convergence for $\sigma <\sigma _{a}$ we would have found a lower upper bound due to the above argument, contradicting the definition of $\sigma _{a}$.$\Box$

Theorem 5.3 (abscissa of conditional convergence):

Formulas

Theorem 8.4 (Euler product):

Let $f$ be a strongly multiplicative function, and let $s\in \mathbb {C}$ such that the corresponding Dirichlet series converges absolutely. Then for that series we have the formula

$\sum _{n=1}^{\infty }{\frac {f(n)}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-{\frac {f(p)}{p^{s}}}}}$.

Proof:

This follows directly from theorem 2.11 and the fact that $f$ strongly multiplicative $\Rightarrow$ ${\frac {f(n)}{n^{s}}}$ strongly multiplicative.$\Box$

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

$\mathrm{\phi <!--\; \phi \; -->}(n)=n\underset{j=1}{\overset{r}{\prod <!--\; \prod \; -->}}$