Multiplicative Function

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

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

For example, the following functions are multiplicative:

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

#StepsComments
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.