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