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.