As usual, let denote the set of the positive integers. A function defined on is said to be *multiplicative* if for every pair of coprime integers . Many well-known arithmetic functions are multiplicative, for instance:

- The number of divisors of :
- The sum of divisors of :
- More generally, the sum of the -th powers of the divisors of : (note that and )
- Euler’s function, : the number of positive integers not exceeding that are coprime to

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

Many arithmetic functions can be represented as

for some arithmetic function . For example, , , or , in general.

**Lemma.** If

and is multiplicative, then so is .

*Proof.* For coprime,

This little lemma shows that , , or in general, is multiplicative for each .

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

Let us first consider the divisor function . Let be coprime. Note that each divisor of is of the form where and ; further, each such pair corresponds to a unique divisor of . Thus there is a bijection between the sets

and

which implies . And the same idea works for in general.

Okay that actually wasn’t different from our previous proof. But the next one will be! Consider the Euler function this time. Again, let be coprime. Let denote the set of elements from that are coprime to . If is coprime to , then is coprime to each of . Further, each pair corresponds to a unique by the Chinese remainder theorem (in modern notation we write

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

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

- Take a hypothetical multiplicative function
- Find a set such that
- Find a bijection between and for coprime .

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

### Like this:

Like Loading...

*Related*

Pingback: An inequality involving sigma and tau | Samin Riasat's Blog