Multiplicative function
A multiplicative function \(f\) is an arithmetic function satisfying \(f(1)=1, f(ab)=f(a)f(b)\) for co-prime integers \(a\) and \(b.\) A completely multiplicative function satisfies \(f(ab)=f(a)f(b)\) for all values of \(a\) and \(b.\)
Multiplicative functions arise naturally in many contexts in number theory and algebra. The Dirichlet series associated with multiplicative functions have useful product formulas, such as the formula for the Riemann zeta function.
Contents
Important multiplicative functions
Here are important multiplicative functions:
- Euler's totient function: \( \phi(n) = \) the number of positive integers \( a\le n \) such that gcd\((a,n)=1 \)
- The Möbius function: \( \mu(n)\)
- The sum of \(\alpha^\text{th}\) powers of divisors: \(\sigma_\alpha(n) = \sum_{d|n} d^\alpha \)
- The function \(e(n) = \left\lfloor\frac{1}{n}\right\rfloor = \begin{cases} 1&\text{if} \ n = 1 \\ 0&\text{otherwise} \end{cases}\)
- The unit function: \( \mathbf{1}(n)=1 \)
- The identity function: \( I(n) = n \)
These last three are completely multiplicative as well.
Values on prime powers
Proof:If \( f \) is a multiplicative function, then it is completely determined by its values \( f(p^k)\) on prime powers. If \( f \) is completely multiplicative, then it is completely determined by its values \(f(p)\) on primes. \(_\square\)
This follows from unique factorization: write \( n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \) for some nonnegative \( k \), primes \( p_i \), and positive integers \( \alpha_i \). Then \[ \begin{align} f(n) &= f(p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}) \\ &= f(p_1^{\alpha_1}) f(p_2^{\alpha_2}) \cdots f(p_k^{\alpha_k}) \\ &= \prod_{i=1}^k f(p_i^{\alpha_i}) \end{align} \] because the prime powers \( p_i^{\alpha_i} \) are all relatively prime to each other. So \( f(n) \) is the product of the values of \( f(p_i^{\alpha_i}) \). If \( f \) is completely multiplicative, then \( f(p_i^{\alpha_i}) = f(p_i)^{\alpha_i} \), so \( f(n) \) is determined by the values of \( f(p_i) \). \( _\square \)
Connection with Dirichlet convolution
If \(f \) and \( g \) are multiplicative functions, then the Dirichlet convolution \( f*g \) is also multiplicative.
Proof:
Write \[ (f*g)(ab) = \sum_{d|ab} f(d)g(ab/d). \] Suppose \( a \) and \( b \) are relatively prime. The key observation is that divisors \( d \) of \(ab\) can be written uniquely as \( d=rs \), where \( r|a \) and \( s|b \). (You can see this by writing down prime factorizations of \( a \) and \( b \) and noting that the primes they decompose into don't overlap, since they're relatively prime.) So \[ \begin{align} (f*g)(ab) &= \sum_{r|a,s|b} f(rs)g(ab/rs) \\ &= \sum_{r|a,s|b} f(r)f(s)g(a/r)g(b/s) \\ &= \sum_{r|a} f(r)g(a/r) \sum_{s|b} f(s)g(b/s) \\ &= (f*g)(a)(f*g)(b), \end{align} \] since \( r \) and \( s \) are relatively prime, and \( a/r \) and \( b/s \) are relatively prime. \( _\square \)
Examples and applications
The techniques of the first theorem can be used to write product formulas for multiplicative functions. For instance, consider the multiplicative function \( \phi(n)/n \). When \( n = p^k \) this evaluates to \( \frac{p^k-p^{k-1}}{p^k} = 1-\frac1{p} \), so \[ \frac{\phi(n)}{n} = \prod_{\substack{p|n \\ p \ \text{prime}}} \left( 1 - \frac1{p} \right). \]
Letting \( n = p_1^{\alpha_1} \cdots p_k^{\alpha_k} \), the following formulas can be derived in a similar way: \[ \begin{align} \sigma_0(n) &= \prod_{i=1}^k (1+\alpha_i) \\ \sigma_r(n) &= \prod_{i=1}^k \frac{p_i^{r(\alpha_i+1)}-1}{p_i^r-1} \quad (r \in {\mathbb N}). \\ \end{align} \]
The two theorems taken together can be used to derive several interesting identities involving multiplicative functions. The first theorem implies that two multiplicative functions that agree on prime power arguments must be the same function. This is useful for proofs.
Let \( \omega(n) = \) the number of distinct prime factors of \(n \). Let \( \text{rad}(n) = \) the product of the distinct prime factors of \( n \). Show that \( \sum_{d|n} \mu(d)\sigma_0(d) = (-1)^{\omega(n)} \text{rad}(n). \)
Proof: The product of multiplicative functions is clearly multiplicative, so \( \mu\sigma_0 \) is multiplicative. The sum on the left is the Dirichlet convolution \( \mu\sigma_0 * \mathbf{1} \), so it is multiplicative by the second theorem. The product on the right is also multiplicative, as it is easy to check that both \( (-1)^{\omega(n)} \) and \( \text{rad}(n) \) are multiplicative functions.
So it suffices to show the theorem is true for \( n = p^k \), \( p \) prime. In this case the left side is \( 1 + -(p+1) = -p \) and the right side is \( (-1)^1 p = -p \), so the two sides agree on prime powers and hence agree everywhere. \(_\square \)
Show that \( \sum_{d|n} \sigma_0(d^2) = \sigma_0(n)^2. \)
Proof: Both sides are multiplicative (similarly to the previous example), so it is enough to check that they agree for \( n = p^k \). In this case, the left side is \[ 1+3+5+\cdots+(2k+1) \] and the right side is \[ (k+1)^2, \] but it is easy to check that these are equal. \(_\square \)
Compute \[ \large \sum_{d|2015!}\mu(d)\phi(d).\]
Notations
- \(\mu(d)\) denotes the Möbius function.
- \(\phi(d)\) denotes Euler's totient function.
- \(d\) are the positive factors of \(2015!.\)