Arithmetic functions I: Dirichlet convolution and Euler's totient function

An arithmetic function is a real or complex-valued functions defined on the set of positive integers. Often, arithmetic functions reflect arithmetical information concerning integers and are intensively studied in number theory.

Defintion. An arithmetic function $f$ is said to be multiplicative if $f(1) = 1$ and $f(mn) = f(m)f(n)$ whenever $m$ and $n$ are relatively prime.

By unique factorization of integers, a multiplicative arithmetic function is determined completely by its values on all of the prime powers.

Examples. (i) Identity function $id$: $id(n) = n$.
(ii) Delta function $\delta$: $\delta(1) = 1, \delta(n) = 0$ for $n > 1$.
(iii) Constant one function $\mathbf{1}$: $\mathbf{1}(n) = 1$.
(iv) Moebius function $\mu$: $\mu(1) = 1$ and if $n$ is the product of $m$ distinct primes, then $\mu(n) = (-1)^m$, otherwise $\mu(n) = 0$.

The set of all multiplicative functions can be made into a commutative ring with identity with pointwise addition and the Dirichlet convolution defined below as multiplication.

Definition. Let $f$ and $g$ be multiplicative functions. The Dirichlet convolution of $f$ and $g$ is the arithmetic function $f * g$ defined by $$f * g(n) = \sum_{d \mid n} f(d)g(\frac{n}{d}).$$

Proposition. Let $f, g, h$ be multiplicative functions.
(i) $f * g$ is multiplicative.
(ii) $(f * g) * h = f * (g * h)$.
(iii) $f * g = g * f$.
(iv) $f * \delta = f$.

Hence the multiplicative identity for Dirichlet convolution is the delta function. Below we see that the multiplicative inverse of constant one function is Moebius function.

Proposition. $\mu * \mathbf{1} = \delta$.
Proof: Firstly, $\mu * \mathbf{1}(1) = \sum_{d \mid 1} \mu(d) = \mu(1) = 1 = \delta(1)$. Now let $n > 1$ with prime factorization $n = p_1^{k_1} \cdots p_m^{k_m}$. Then  $$\begin{align*} \mu * \mathbf{1}(n) &= \sum_{d \mid n} \mu(d) \\ &= \mu(1) + \mu(p_1) + \cdots + \mu(p_m) + \mu(p_1 p_2) + \cdots + \mu(p_{m - 1} p_m) + \cdots + \mu(p_1 \cdots p_m) \\ &= 1 + \binom{m}{1} (-1) + \binom{m}{2} (-1)^2 + \cdots + \binom{m}{m} (-1)^m \\ &= (1 - 1)^m = 0 = \delta(n). \end{align*}$$ Q. E. D.

We now introduce an important arithmetic function in number theory, Euler's totient function $\phi$. For a positive integer $n$, $\phi(n)$ is the number of integers from 1 to $n$ which are relative prime to $n$.

Theorem. $\phi = \mu * id$.
Proof:  $$\begin{align*} \phi(n) &= \sum_{1 \leq k \leq n, (k, n) = 1} 1 = \sum_{k = 1}^n \delta((k, n)) \\ &= \sum_{k = 1}^n \mu * \mathbf{1}((k, n)) \\ &= \sum_{k = 1}^n \sum_{d \mid (k, n)} \mu(d) \\ &= \sum_{k = 1}^n \sum_{d \mid k, d \mid n} \mu(d) \\ &= \sum_{d \mid n} \sum_{1 \leq k \leq n, d \mid k} \mu(d) \\ &= \sum_{d \mid n} \sum_{1 \leq k \leq n, k = dm} \mu(d) \\ &= \sum_{d \mid n} \sum_{1 \leq m \leq n/d} \mu(d) \\ &= \sum_{d \mid n} \mu(d) \frac{n}{d} \\ &= \mu * id(n). \end{align*}$$ Q. E. D.

Corollary. $\phi$ is multiplicative.

Another corollary is the classical formula by Euler.

Corollary. $\sum_{d \mid n} \phi(d) = n$, i.e, $\phi * \mathbf{1} = id$.
Proof: $\phi * \mathbf{1} = (\mu * id) * \mathbf{1} = (\mu * \mathbf{1}) * id =  \delta * id = id$. Q. E. D.

Now we derive a formula for Euler's totient function in terms of prime factorizations.

Lemma. For a prime $p$ and positive integer $k$, $\phi(p^k) = p^k - p^{k - 1}$.
Proof: It suffices to note that the numbers between 1 and $p^k$ not relative prime to $p^k$ are $p, 2p, 3p,  \ldots, p^{k - 1} \cdot p$. Q. E. D.

Theorem. Let $n > 1$ with prime factorization $n = p_1^{k_1} \cdots p_m^{k_m}$. Then $$\phi(n) = n(1 - \frac{1}{p_1}) \cdots (1 - \frac{1}{p_m}).$$
Proof: $\phi(n) = \prod_{j = 1}^m (p_j^{k_j} - p_j^{k_j - 1}) = \prod_{j = 1}^m p_j^{k_j} (1 - \frac{1}{p_j}) = n \prod_{j = 1}^m (1 - \frac{1}{p_j})$. Q. E. D.

Reference:
Apostol - Introduction to Analytic Number Theory