Tag Archives: arithmetic function

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.


1 Comment

Filed under Combinatorics, Number theory