# A combinatorial approach to multiplicative functions

As usual, let $\mathbb N$ denote the set of the positive integers. A function $f$ defined on $\mathbb N$ is said to be multiplicative if $f(mn)=f(m)f(n)$ for every pair of coprime integers $m,n\in\mathbb N$. Many well-known arithmetic functions are multiplicative, for instance:

1. The number of divisors of $n$: $\tau(n)$
2. The sum of divisors of $n$: $\sigma(n)$
3. More generally, the sum of the $k$-th powers of the divisors of $n$: $\sigma_k(n)$ (note that $\tau(n)=\sigma_0(n)$ and $\sigma(n)=\sigma_1(n)$)
4. Euler’s function, $\varphi(n)$: the number of positive integers not exceeding $n$ that are coprime to $n$

And many more. (See here for a more comprehensive list.)

Many arithmetic functions $F(n)$ can be represented as

$\displaystyle F(n)=\sum_{d\mid n}f(d)$

for some arithmetic function $f(n)$. For example, $\displaystyle \tau(n)=\sum_{d\mid n} 1$, $\displaystyle \sigma(n)=\sum_{d\mid n} d$, or $\displaystyle \sigma_k(n)=\sum_{d\mid n} d^k$, in general.

Lemma. If

$\displaystyle F(n)=\sum_{d\mid n}f(d)$

and $f$ is multiplicative, then so is $F$.

Proof. For $m,n$ coprime,

$\displaystyle F(mn)=\sum_{d\mid mn}f(d)=\sum_{\substack{d_1\mid m\\ d_2\mid n}}f(d_1d_2)$

$\displaystyle=\sum_{\substack{d_1\mid m\\ d_2\mid n}}f(d_1)f(d_2)=\sum_{d_1\mid m}f(d_1)\sum_{d_2\mid n}f(d_2)=F(m)F(n).\quad \square$

This little lemma shows that $\tau(n)$, $\sigma(n)$, or $\sigma_k(n)$ in general, is multiplicative for each $k$.

However, my original intention was to illustrate a combinatorial reasoning proving that these functions are multiplicative!

Let us first consider the divisor function $\tau(n)$. Let $m,n$ be coprime. Note that each divisor of $mn$ is of the form $d_1d_2$ where $d_1\mid m$ and $d_2\mid n$; further, each such pair $(d_1,d_2)$ corresponds to a unique divisor of $n$. Thus there is a bijection between the sets

$\{d:d\mid mn\}$ and $\{(d_1,d_2):d_1\mid m, d_2\mid n\}$

which implies $\tau(mn)=\tau(m)\tau(n)$. And the same idea works for $\sigma_k(n)$ in general.

Okay that actually wasn’t different from our previous proof. But the next one will be! Consider the Euler function $\varphi(n)$ this time. Again, let $m,n$ be coprime. Let $(\mathbb Z/n\mathbb Z)^\times$ denote the set of elements from $\{1,2,\dots,n\}$ that are coprime to $n$. If $a$ is coprime to $mn$, then $a$ is coprime to each of $m,n$. Further, each pair $(a_1,a_2)\in (\mathbb Z/m\mathbb Z)^\times\times(\mathbb Z/n\mathbb Z)^\times$ corresponds to a unique $a\in(\mathbb Z/mn\mathbb Z)^\times$ by the Chinese remainder theorem (in modern notation we write

$\displaystyle (\mathbb Z/mn\mathbb Z)^\times\cong(\mathbb Z/m\mathbb Z)^\times\times(\mathbb Z/n\mathbb Z)^\times$

as groups.) Thus we have a bijection between the sets, and so

$\varphi(mn)=|(\mathbb Z/mn\mathbb Z)^\times|=|(\mathbb Z/m\mathbb Z)^\times|\cdot |(\mathbb Z/mn\mathbb Z)^\times|=\varphi(m)\varphi(n)$

The underlying strategy in the above proofs can be outlined as follows:

1. Take a hypothetical multiplicative function $f(n)$
2. Find a set $S(n)$ such that $f(n)=|S(n)|$
3. Find a bijection between $S(mn)$ and $S(m)\times S(n)$ for coprime $m,n$.

If we want to show that a function is totally multiplicative, we can replace ‘coprime’ by ‘arbitrary’ in 3.