Chapter 2

Arithmetic functions

2.1 Multiplicative and additive functions

A complex-valued function defined on N∗ is called an arithmetic function.

Definition 2.1 (Multiplicative/Additive functions). Let f : N∗ → C be an arithmetic

function. We say f is multiplicative if f is not identically zero and satisfies

f (mn) = f (m)f (n) (2.1)

whenever (m, n) = 1. If (2.1) holds unconditionally for all m, n, we say f is com-

pletely multiplicative.
Similarly, an arithmetic funtion f is additive if

f (mn) = f (m) + f (n) (2.2)

whenever (m, n) = 1. Moreover, if (2.2) holds unconditionally for all m, n, we say

f is completely additive.

A multiplicative function f satisfies f (1) = 1. In fact, since a multiplicative

function is not identically zero, there exists some n ∈ N∗ s.t. f (n) 6= 0. Then we can
deduce f (1) = 1 from f (n) = f (n)f (1).
A multiplicative function reflects the multiplicative structure of N∗ . Let f be a
multiplicative function and let n = pα1 1 · · · pαk k be the prime factorization of n. Then
we have
f (n) = f (pα1 1 ) · · · f (pαk k ). (2.3)

13
14 CHAPTER 2. ARITHMETIC FUNCTIONS

Conversely, by assigning a value for each f (pα ), we can uniquely define a multiplica-
tive function by (2.3).
If we further assume that f is completely multiplicative, then we have

f (n) = f (p1 )α1 · · · f (pk )αk .

So a completely multiplicative function is determined by its value on each prime

number.

2.2 Examples
The following arithmetic functions are classical and define fundamental concepts
attached to the multiplicative structure of N∗ .

1). The divisor function, counting the number of positive divisors of n, is tradition-
ally denoted by X
τ (n) = 1.
d|n

Similarly, we can define the function of the sum of k-th power divisors of n, which
is denoted by X
σk (n) = dk , k ∈ C.
d|n

Thus τ (n) = σ0 (n) and usually we write σ(n) for σ1 (n). The function σk (n) is
multiplicative. In fact, assuming that (m, n) = 1, any divisor d of mn can be
uniquely decomposed into d = d1 d2 with d1 | m and d2 | n. So
  
X XX X X
σk (mn) = dk = dk1 dk2 =  dk1   dk2  = σk (m)σk (n).
d|mn d1 |m d2 |n d1 |m d2 |n

By (2.3), if n = pα1 1 · · · pαk k , we have

τ (n) = (1 + α1 ) · · · (1 + αk )

2). Euler’s totient function φ(n), counting the number of invertible residues modulo
n, is denoted by X
φ(n) = (Z/nZ)× = 1.
1≤d≤n
(d,n)=1
2.2. EXAMPLES 15

For (m, n) = 1, we have

Z/mnZ ∼
= Z/mZ ⊕ Z/nZ ⇒ (Z/mnZ)× ∼
= (Z/mZ)× ⊕ (Z/nZ)× .

By considering the cardinal of both sides, we get φ(mn) = φ(m)φ(n). Thus φ(n)
is multiplicative.

3). Suppose that n = pα1 1 · · · pαk k . Define

ω(n) = k, Ω(n) = α1 + · · · + αk .

That is, Ω(n) is the number of primes factors of n and ω(n) is the number of
distinct prime factors of n. Clearly, ω(n) is additive and Ω(n) is completely
additive.

4). The Liouville function is defined by

λ(n) = (−1)Ω(n) .

Since Ω(n) is completely additive, λ(n) is completely multiplicative.

5). The Möbius function is defined by

(
(−1)k , n = p1 · · · pk , p1 , . . . , pk are distinct prime numbers
µ(n) =
0, otherwise (i.e. n is not square-free).

Note that for coprime m, n, mn is square-free if and only if both m and n are
square-free. So it is not hard to see that µ(n) is multiplicative. The Möbius
function plays an important role in the distribution of prime numbers.

6). The Von Mangoldt function Λ(n) is defined by

(
log p, n = pk , p is prime, k ∈ N∗
Λ(n) =
0, otherwise.

Roughly speaking, Λ(n) is a weighted characteristic function of the set of prime

numbers.
16 CHAPTER 2. ARITHMETIC FUNCTIONS

2.3 The Dirichlet convolution

For an arithmetic function f , define the formal Dirichlet series associated with f
by the formal series
X∞
f (n)
D(f ; s) = s
.
n=1
n
Let f and g be arithmetic functions. A formal computation gives
! !
X∞
f (m1 ) X
∞
g(m2 ) X∞ X ∞
f (m1 )g(m2 )
D(f ; s)D(g; s) = s s
=
m1 =1
m1 m2 =1
m2 m1 =1 m2 =1
ms1 ms2
!
X∞
1 X
= s
f (m1 )g(m2 ) .
n=1
n m m =n
1 2

So the product of D(f ; s) and D(g; s) should be defined as the formal Dirichlet series
D(h; s) associated with h where h is the arithmetic function given by
X X n X n
h(n) = f (m1 )g(m2 ) = f (d)g = g(d)f .
m m =n
d d
1 2 d|n d|n

This arithmetic function h is called the Dirichlet convolution of f and g and is

denoted by f ∗ g.
For arithmetic functions f and g, we define
(
D(f ; s) + D(g; s) = D(f + g; s)
(2.4)
D(f ; s)D(g; s) = D(f ∗ g; s).

It is not hard to see that the set of all formal Dirichlet series equipped with these
two operation has the structure of commutative ring with unity given by the series
D(δ; s) associated with the arithmetic function
(
1, n = 1
δ(n) =
0, n > 1.

A formal Dirichlet series D(f ; s) is uniquely determined by the arithmetic function

f . So we see from (2.4) that the set of arithmetic functions, equipped with the usual
addition operation and the Dirichlet convolution, has the structure of a commutative
ring isomorphic to that of formal Dirichlet series.
2.3. THE DIRICHLET CONVOLUTION 17

Proposition 2.1. The group of units in the ring of arithmetic functions consists of
arithmetic functions f such that f (1) 6= 0.
Proof. If f is invertible with the convolution inverse g, then we have
f (1)g(1) = δ(1) = 1.
So f (1) 6= 0. Conversely, if f (1) 6= 0, we can recursively calculate the convolution
inverse g of f . In fact, the arithmetic function g defined by
X n
g(1) = f (1)−1 , g(n) = −f (1)−1 g(d)f , n>1 (2.5)
d
d|n
d<n

clearly satisfies f ∗ g = δ.
Proposition 2.2. The set of multiplicative functions is a subgroup of the group of
units in the ring of arithmetic functions.
Proof. We need to show that
1). The Dirichlet convolution of multiplicative functions is multiplicative.
2). The convolution inverse of a multiplicative function is multiplicative.
Proof of 1). Let f and g be multiplicative functions. Suppose that (m, n) = 1. Then
X  mn  X X  
mn
(f ∗ g)(mn) = f (d)g = f (d1 d2 )g
d d1 d2
d|mn d1 |m d2 |n
  
X   X  
m  n 
= f (d1 )g f (d2 )g
d1 d2
d1 |m d2 |n

= (f ∗ g)(m) · (f ∗ g)(n).
Proof of 2). Let f be a multiplicative function. Then we have f (1) = 1 (see the
dicussion under the definition of multiplicative functions). Thus f is invertible by
Proposition 2.1. Let g be the inverse of f . We should prove that
(m, n) = 1 ⇒ g(mn) = g(m)g(n).
We prove by induction on mn. For mn = 1, it suffices to show that g(1) = 1. This
is quite obvious since we have
f (1)g(1) = δ(1) = 1.
18 CHAPTER 2. ARITHMETIC FUNCTIONS

Now assume that mn > 1 and the multiplicativity of g holds for smaller mn. Then
we have
0 = δ(mn) = (f ∗ g)(mn)
X  mn 
= f (d)g
d
d|mn
XX  
mn
= f (d1 d2 )g
d1 d2
d1 |m d2 |n
XX    
m n
= f (d1 )f (d2 )g g + g(mn)
d1 d2
d1 |m d2 |n
d1 d2 >1
XX    
m n
= f (d1 )f (d2 )g g − g(m)g(n) + g(mn)
d1 d2
d1 |m d2 |n

= δ(m)δ(n) − g(m)g(n) + g(mn).

Since mn > 1, we have δ(m)δ(n) = 0. So g(mn) = g(m)g(n).

Example 2.1. Let 1 denote the function 1(n) = 1. Then we have τ = 1 ∗ 1 and
σk = nk ∗ 1. So we regain the multiplicativity of τ and σk .

Theorem 2.3. Let f be a multiplicative function. Then we have

X Y
f (d) = (1 + f (p) + · · · + f (pα )) ,
d|n pα ||n

Y
where the notation means taking the product of all prime factor p of n and
pα ||n
vp (n) = α.

Proof. By Proposition 2.2, X

f (d) = (f ∗ 1)(n)
d|n

is a multiplicative function in n. So we have

X YX Y
f (d) = f (d) = (1 + f (p) + · · · + f (pα )) .
d|n pα ||n d|pα pα ||n
2.4. THE MÖBIUS INVERSION FORMULA 19

2.4 The Möbius inversion formula

Proposition 2.4. The Möbius function is the convolution inverse of 1, that is,
1 ∗ µ = δ. In other words,
(
X 1, n = 1
µ(d) =
d|n
0, n > 1.

Proof. Suppose that n = pα1 1 · · · pαk k , n > 1 (i.e. k 6= 0). Then

X k  
X k
(µ ∗ 1)(n) = µ(d) = (−1)j = (1 − 1)k = 0.
j=0
j
d|n

P
We explain the occurance of binomial numbers. In the sum d|n , given 0 ≤ j ≤ k,


there are exactly kj choices of square-free d such that d has exactly j distinct prime


factors. These d contributes kj (−1)j .

We provide an alternative proof. This method is useful in checking an identity

of multiplicative functions.

Proof. By Proposition 2.2, both δ ∗ 1 and δ are multiplicative. So we need only to

verify
(µ ∗ 1)(pα ) = δ(pα ) = 0
for each prime power pα . In fact, we have

(µ ∗ 1)(pα ) = 1 + (−1) + 0 + · · · + 0 = 0.

For a completely multiplicative functions, its Dirichlet inverse can be easily com-
puted:

Theorem 2.5. Let f be a multiplicative function. Then f is completely multiplicative

if and only if
f −1 (n) = µ(n)f (n),
where f −1 (n) is the Dirichlet inverse of f (should not be confused with f (n)−1 =
1/f (n)).
20 CHAPTER 2. ARITHMETIC FUNCTIONS

Proof. Recall that f (1) = 1 since f is multiplicative. Suppose that f is completely

multiplicative, then we have
X n X
(f ∗ µf )(n) = µ(d)f (d)f = f (n) µ(d) = f (n)δ(n) = δ(n).
d
d|n d|n

Conversely, suppose
f −1 (n) = µ(n)f (n).
To show f is completely multiplicative, it suffices to prove

f (pα ) = f (p)α

for any prime power pα . By taking n = pα in

X n
µ(d)f (d)f = δ(n),
d
d|n

we obtain
f (pα ) = f (p)f (pα−1 ).
Hence
f (pα ) = f (p)f (pα−1 ) = f (p)2 f (pα−2 ) = · · · = f (p)α .

Theorem 2.6 (Möbius inversion formula). Let f and g be arithmetic functions.

Then the following statements are equivalent:
X
1). g(n) = f (d), ∀n ≥ 1.
d|n

X n
2). f (n) = µ(d)g , ∀n ≥ 1.
d
d|n

Proof. We need to show that

g =f ∗1 ⇔ f = g ∗ µ.

By Proposition 2.4, we have

g =f ∗1 ⇔ g ∗ µ = f ∗ 1 ∗ µ = f ∗ δ = f.

This completes the proof.

2.4. THE MÖBIUS INVERSION FORMULA 21

Remark. Certainly, we can replace the function 1 by any other completely multi-
plicative function, and apply Theorem 2.5 to get other inversion formulas. Specif-
ically, suppose w(n) is a completely multiplicative function. By Theorem 2.5, we
have w−1 = µw. So for any arithmetic funtions f and g, we have
g =f ∗w ⇔ f = g ∗ µw.
That is, X n
g(n) = f (d)w
d
d|n

is equivalent to X n
f (n) = µ(d)w(d)g .
d
d|n

Taking w = 1, we get Theorem 2.6.

Theorem 2.7 (Generalized Möbius inversion formula). Let F and G be functions
on [1, +∞). Then the following statements are equivalent:
X x
i). G(x) = F , ∀x ≥ 1.
n≤x
n
X x
ii). F (x) = µ(n)G , ∀x ≥ 1.
n≤x
n
X x
Proof. i) ⇒ ii). Suppose that G(x) = F . Then we have
n≤x
n
X x X X  x  X x X
µ(n)G = µ(n) F = F µ(n),
n≤x
n n≤x x mn k≤x
k mn=k
m≤ n

where we have rearraged the sum by putting together those m, n with the same
product. By Proposition 2.4, we have
X
µ(n) = δ(k).
mn=k
So we finally obtain that
X x X x
µ(n)G = F δ(k) = F (x).
n≤x
n k≤x
k
A similar argument gives ii) ⇒ i), which is left as an exercise for readers.
Corollary 2.8. We have X hxi
µ(n) = 1.
n≤x
n
22 CHAPTER 2. ARITHMETIC FUNCTIONS

2.5 Applications
Theorem 2.9. We have
X n Y 1

φ(n) = µ(d) = n 1− .
d p
d|n p|n

Hence by the Möbius inversion formula, we obtain the well-known fact that
X
φ(d) = n.
d|n

Proof. The relation µ ∗ 1 = δ provides a useful trick to deal with the condition
(m, n) = 1:
Xn X n Xn X
φ(n) = 1= δ((m, n)) = µ(d)
m=1 m=1 m=1 d|(m,n)
(m,n)=1
Xn X X X
n
= µ(d) = µ(d) 1
m=1 d|m d|n m=1
d|n d|m
X n
= µ(d) .
d
d|n

Since µ(n)/n is multiplicative, we have

X n X µ(d) Y 1

φ(n) = µ(d) = n =n 1− .
d d p
d|n d|n p|n

Remark. We provide an alternative way to derive the identity

X
φ(d) = n.
d|n

Notice that each rational fraction in (0, 1] with denominator n can be written in the
form h/n = a/d with (a, d) = 1. Thus
X X X X
n= 1= 1= φ(d).
1≤h≤n d|n 1≤a≤d d|n
(a,d)=1
2.5. APPLICATIONS 23

Theorem 2.10. Let Λ be the Von Mangoldt function. Then we have

X
Λ(d) = log n.
d|n

As a consequence,
X n X
Λ(n) = µ(d) log =− µ(d) log d.
d
d|n d|n

Proof. Suppose that n = pα1 1 · · · pαk k . Note that Λ(d) = log p if d is a power of the
prime p and Λ(d) = 0 otherwise. So

X X
k X
k
α
Λ(d) = αj log pj = log pj j = log n.
d|n j=1 j=1

The second assertion follows from the Möbius inversion formula.

Theorem 2.11. Let 1□ denote the characteristic function of squares, i.e.

(
1, n = k 2 for some k ∈ N∗ ,
1□ (n) =
0, otherwise.

Then we have 1□ = λ ∗ 1, where λ is the Liouville function. As a consequence, we

have X n
λ(n) = µ(d)1□ .
d
d|n

Proof. Since λ ∗ 1 is multiplicative, it suffices to consider the value of λ ∗ 1 at each

prime powers. By the definition of λ, we have
(
1, α is even
(λ ∗ 1)(pα ) =
0, α is odd.

The desired result follows.

We have defined the formal Dirichlet series in Section 2.3. We call
X
∞
f (n)
D(f ; s) =
n=1
ns
24 CHAPTER 2. ARITHMETIC FUNCTIONS

the Dirichlet series associated with f if it is convergent. The Dirichlet series

associated with 1 is called the Riemann ζ-function:
X∞
1
ζ(s) = .
n=1
ns

It is absolutely convergent for Re s > 1.

Theorem 2.12. For Re s > 1, we have

1 X µ(n)
∞
= .
ζ(s) n=1 ns

Hence ζ(s) 6= 0 for Re s > 1.

Proof. It follows from µ−1 = 1 and |µ(n)| ≤ 1.

Theorem 2.13. For Re s > 1, we have

ζ ′ (s) X Λ(n)
∞
− = .
ζ(s) n=1
ns

Proof. The series

X∞
1
n=1
ns
is convergent uniformly in any compact subset of the set {s ∈ C : Re s > 1}. Thus
we can take the derivative term by term. So we have
X
∞
log n
′
−ζ (s) = .
n=1
ns

By Theorem 2.12 and Theorem 2.10,

! ∞ !
ζ ′ (s) X∞
log n X µ(n) X∞
(µ ∗ log)(n) X Λ(n)
∞
− = = = .
ζ(s) n=1
ns n=1
ns n=1
ns n=1
ns