# Multiplicative Function

A function $f(n)$ is called multiplicative function if:

- $f(n)$ is defined for positive integer $n$.
- $f(1) = 1$
- $f(mn) = f(m)f(n)$ whenever $gcd(m,n) = 1$.

For example, the following functions are multiplicative:

- Euler Phi – $\phi(n)$
- Number of Divisor – $\sigma_0(n)$
- Sum of Divisor – $\sigma_1(n)$

# Divisor Sum Theorem of Multiplicative Function

Theorem: Let $f(n)$ be a multiplicative function and define $$F(n) = \sum_{d \mid n} f(d)$$

Then $F(n)$ is also multiplicative.

In essence, if we can define a function $F(n)$ as divisor sum of another multiplicative function, it will be enough to prove that $F(n)$ is multiplicative.

## Proof

# | Steps | Comments |
---|---|---|

Let $m$ and $n$ be positive integer and $gcd(m,n) = 1$ | ||

Let $f(n)$ be a multiplicative function as defined in the theorem above | ||

1 | $$F(mn) = \sum_{d \mid mn} f(d)$$ | As defined in the theorem |

Let $d = rs$, where $r \mid m$ and $s \mid n$ | ||

Also, since we know that there is no common divisor of $m$ and $n$, we can say that $gcd(r,s) = 1$ | ||

2 | $$ = \sum_{r \mid m, s \mid n} f(rs)$$ | |

Since $f(n)$ is multiplicative and we know that $gcd(r,s) = 1$, we can say that $f(rs) = f(r)f(s)$ | ||

3 | $$ = \sum_{r \mid m, s \mid n} f(r)f(s)$$ | |

4 | $$ = \sum_{r \mid m} f(r) \sum_{s \mid n} f(s)$$ | |

5 | $$ = F(m)F(n)$$ | Proved ðŸ™‚ |

Therefore, if a function $F(n)$ can be written as divisor sum of a multiplicative function $f(n)$, then $F(n)$ is also a multiplicative.

## Application

The Divisor Sum Theorem is useful in proving that a function $F(n)$ is multiplicative. For example, this theorem is used in proving that GCD Sum Function is multiplicative.

# Conclusion

Often time it is difficult to calculate the value of $f(n)$ when $n$ is composite but easy to calculate when $n$ is a power of a prime, $p^a$. In such scenarios, life becomes much easier if we can prove that $f(n)$ is multiplicative.