16 1. Arithmetic Functions
1.5. Sums over divisors
We remind the reader that an arithmetic function f is a mapping f : N → C.
Some arithmetic functions such as log arise by restricting functions of a
real variable to the positive integers. But in most cases of interest f(n) is
determined by arithmetical information about the integer n. The divisor
function d(n) given as the number of positive divisors of the positive integer
n is an example. Each positive integer n has a unique factorization
n = p1
· · ·pr
into primes and the divisors d of n are the integers of the form
d = p11
· · ·pr
where the βj are integers satisfying 0 ≤ βj ≤ αj for j = 1, 2,...,r. Hence
d(n) = (α1 +1)(α2 +1) · · · (αr +1) is a formula for the divisor function d(n)
given in terms of the prime factorization of n.
An arithmetic function f is additive if f(mn) = f(m) + f(n) when-
ever gcd(m, n) = 1. It is multiplicative if f ≡ 0 and f(mn) = f(m)f(n)
whenever gcd(m, n) = 1. It is totally additive or totally multiplicative if the
corresponding property holds without requiring the condition gcd(m, n) = 1.
A multiplicative or additive function can be unambiguously prescribed by
giving its values on the prime powers, and a totally multiplicative or totally
additive function by giving its values on the primes. Note also that f(1) = 1
if f is multiplicative.
The function log(n) and the function Ω(n) that counts the prime divisors
of n with multiplicity are totally additive. The function ω(n) that counts
the distinct prime divisors of n is additive, but not totally additive. The
identity function id given by n → n is totally multiplicative. So is the
The divisor function d(n) is multiplicative, but not totally multiplicative.
The Euler phi-function φ(n) is also multiplicative. Another multiplicative
arithmetic function is the radical
It is also called the squarefree kernel.
The von Mangoldt function Λ(n) is an important arithmetic function
that is neither additive nor multiplicative.
The product of two multiplicative functions is multiplicative and the
sum of two additive functions is additive. But a more important algebraic