The infinitude of prime numbers had been well known since Euclid. A stronger result is that the following series diverges: \[\sum_p \frac{1}{p} \rightarrow \infty.\]
Suppose the series above converges, i.e. there is a \(q\) such that \[\sum_{p>q} \frac{1}{p} < \frac{1}{2}.\] Then we let \(p_1,\cdots,p_m\) denotes all prime numbers less than \(q\), and let \[Q = p_1 \cdots p_m.\] Now since \(\{1+nQ\}\) are not divisible by \(p_1,\cdots,p_m\), we find that \[\sum_{n=1}^r \frac{1}{1+nQ} \le \sum_{i=1}^\infty (\sum_{p>q} \frac{1}{p})^i\] since every item on the LHS is included in the summation on the RHS. This yields a contradiction.
We define \(\operatorname{id}_k(n) = n^k\), and \(\operatorname{id}(n) = n\).
Definition. \(\displaystyle (f * g)(n) = \sum_{d | n} f(d) g\qty(\frac{n}{d}).\)
Under this definition, the commutation law and the association law hold. \[f*g = g*f,\quad (f*g)*h = f*(g*h).\] The Dirichlet inverse of \(f\) is denoted by \(f^{-1}\) and satisfies \(f^{-1}*f = I\). If \(f(1) \neq 0\), then the inverse exists and is unique.
Definition. The derivative of a arithmetic function is defined by \(f'(n) = f(n)\log n\), for \(n\ge 1\).
Many properties of the derivative in calculus hold for the arithmetic derivative as well.
Multiplicative functions make up a subgroup of arithmetic functions under the binary operation defined by the Dirichlet convolution, i.e. if \(f*g\) is multiplicative if both \(f\) and \(g\) are, and \(f^{-1}\) is multiplicative if \(f\) is.
Examples of multiplcative functions includes
Theorem. Let \(f\) be multiplicative. Then \(f\) is completely multiplicative if and only if \(f^{-1}(n) = \mu(n) f(n)\).
Theorem. If \(f\) is multiplicative, then \[\sum_{d|n} \mu(d) f(d) = \prod_{p|n} (1-f(p)).\]
Definition. \(\displaystyle I(n) = \qty(n) = \begin{cases} 1, & \text{if } n = 1; \\ 0, & \text{if } n > 1.\end{cases}{}\)
This is the analogy of the \(\delta\)-function in number theory. \[I * f = f * I = f.\]
Definition. \(\mu(1) = 1\), and for \(n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1\) we define \[\mu(n) = \begin{cases} (-1)^k, & \text{if } \alpha_1 = \cdots = \alpha_k = 1; \\ 0, & \text{otherwise}. \end{cases}{}\]
Theorem. If \(n\ge 1\) we have \[(1 * \mu)(n) = \sum_{d | n} \mu(d) = I(n) = \qty[\frac{1}{n}] = \begin{cases} 1, & \text{if } n = 1; \\ 0, & \text{if } n > 1. \end{cases}{}\]
Definition. \(\varphi(n)\) is defined to be the number of of integers in \(1,\cdots,n\) that's coprime with \(n\).
Theorem. If \(n\ge 1\) we have \[(1 * \varphi)(n) = \sum_{d | n} \varphi(d) = n.\]
Theorem. If \(n\ge 1\) we have \[(\mu*\operatorname{id})(n) = \sum_{d | n}\mu(d)\frac{n}{d} = \varphi(n).\]
Theorem. \(\varphi\) could be written as the product form \[\varphi(n) = n \prod_{p | n} \qty(1-\frac{1}{p}).\]
Some properties of the totient function are given below.
Theorem. If \(f = 1 * g\), then \(g = f * \mu\).
Definition. \[ \displaystyle \Lambda(n) = \begin{cases}\log p, & \text{if } n = p^m, \text{ where } p \text{ is a prime}, \text{ and } m\ge 1; \\ 0, &\text{otherwise}.\end{cases}{} \]
Theorem. If \(n\ge 1\), \(\displaystyle (1')(n) = \log n = 1 * \Lambda = \sum_{d|n} \Lambda(d)\).
Theorem. If \(n\ge 1\), \(\displaystyle \Lambda(n) = \mu * (1') = -\sum_{d|n} \mu(d) \log d\).
Definition. \(\lambda(1) = 1\), and for \(n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1\) we define \[\lambda(n) = (-1)^{\alpha_1 + \cdots + \alpha_k}.\]
Theorem. For \(n>1\), we have \[ (1 * \lambda)(n) = \sum_{d|n} \lambda(d) = \begin{cases} 1, &\text{if } n \text{ is a perfect square}; \\ 0, & \text{otherwise}. \end{cases} \] We have also \(\lambda^{-1}(n) = \mu^2(n)\).
Definition. \(\sigma_k(n) = \operatorname{id}_k * 1 = \sum_{d|n} d^k\).
In particular, we denote \(\sigma_0(n)\) by \(d(n)\), which counts the number of divisors, and \(\sigma_1(n)\) by \(\sigma(n)\), which is the sum of all divisors.
Theorem. The inversion of the divisor function is given by \[\sigma_k^{-1} = (\mu \operatorname{id}_k)*\mu = \sum_{d|n} d^k \mu(d) \mu\qty(\frac{n}{d}).\]
In the following context, \(F\) is a function on \((0,+\infty)\) that satisfies \(F(x) = 0\) for \(x\in (0,1)\).
Definition. \(\displaystyle (\alpha\circ F)(x) = \sum_{n\le x} \alpha(n) F\qty(\frac{x}{n})\).
Theorem. Let \(\alpha\) and \(\beta\) be arithmetic functions. Then \[ \alpha\circ(\beta\circ F) = (\alpha*\beta)\circ F. \]
Theorem. The generalized inversion formula is given by \[ G = \alpha \circ F \Leftrightarrow F = \alpha^{-1}\circ G. \]
Theorem. For a completely multiplcative \(\alpha\) we have \[ G = \alpha\circ F \Leftrightarrow F = (\mu\alpha)\circ G. \]
Definition. Let \(f\) be a arithmetic function. We define the Bell series of \(f\) modulo \(p\) by the formal power series \[ f_p(x) = \sum_{n=0}^\infty f(p^n) x^n. \]
Examples of Bell series are listed below.
Theorem. Let \(h = f*g\). Then \[h_p(x) = f_p(x) g_p(x).\]
We have the following table of convolution relations of various arithmetic functions.
\(f*g\) | \(I\) | \(1\) | \(\operatorname{id}{}\) | \(\varphi\) | \(\mu\) |
\(I\) | \(I\) | \(1\) | \(\operatorname{id}{}\) | \(\varphi\) | \(\mu\) |
\(1\) | \(1\) | \(d\) | \(\sigma\) | \(\operatorname{id}{}\) | \(I\) |
\(\operatorname{id}{}\) | \(\operatorname{id}{}\) | \(\sigma\) | \(\sigma\cdot \operatorname{id}{}\) | \(\varphi\) | |
\(\varphi\) | \(\varphi\) | \(\operatorname{id}{}\) | |||
\(\mu\) | \(\mu\) | \(I\) | \(\varphi\) |