Number Theory: Structures, Examples, and Problems

I Fundamentals, 6. Arithmetic Functions
Theorem 6.1.1.
The M¨obius function
μ
is multiplicative.
Proof.
Let
m
,
n
be positive integers such that gcd
(
m
,
n
)
=
1. If
p
2
|
m
for some
p
>
1, then
p
2
|
mn
and so
μ(
m
)
=
μ(
mn
)
=
0 and we are done. Consider now
m
=
p
1
· · ·
p
k
,
n
=
q
1
· · ·
q
h
, where
p
1
, . . . ,
p
k
,
q
1
, . . . ,
q
h
are distinct primes.
Then
μ(
m
)
=
(
−
1
)
k
,
μ(
n
)
=
(
−
1
)
h
, and
mn
=
p
1
· · ·
p
k
q
1
· · ·
q
h
. It follows that
μ(
mn
)
=
(
−
1
)
k
+
h
=
(
−
1
)
k
(
−
1
)
h
=
μ(
m
)μ(
n
)
.
For an arithmetic function
f
we define its
summation function F
by
F
(
n
)
=
d
|
n
f
(
d
).
The connection between
f
and
F
is given by the following result.
Theorem 6.1.2.
If f is multiplicative, then so is its summation function F .
Proof.
Let
m
,
n
be positive integers such that gcd
(
m
,
n
)
=
1 and let
d
be a divisor
of
mn
. Then
d
can be uniquely represented as
d
=
kh
, where
k
|
m
and
h
|
n
.
Because gcd
(
m
,
n
)
=
1, we have gcd
(
k
,
h
)
=
1, so
f
(
kh
)
=
f
(
k
)
f
(
h
)
. Hence
F
(
mn
)
=
d
|
mn
f
(
d
)
=
k
|
m
h
|
n
f
(
k
)
f
(
h
)
=
k
|
m
f
(
k
)
h
|
n
f
(
h
)
=
F
(
m
)
F
(
n
).
Remark.
If
f
is a multiplicative function and
n
=
p
α
1
1
· · ·
p
α
k
k
, then
F
(
n
)
=
k
i
=
1
1
+
f
(
p
i
)
+ · · · +
f
(
p
α
i
i
)
.
(
1
)
Indeed, after multiplication on the right-hand side we get a sum having terms
of the form
f
(
p
β
1
1
)
· · ·
f
(
p
β
k
k
)
=
f
(
p
β
1
1
· · ·
p
β
k
k
)
, where 0
≤
β
1
≤
α
1
, . . . ,
0
≤
β
k
≤
α
k
. This sum is obviously
F
(
n
)
.
The function
g
(
n
)
=
μ(
n
)
f
(
n
)
is multiplicative; hence applying (1), we get,
for its summation function
G
,
G
(
n
)
=
k
i
=
1
1
+
μ(
p
i
)
f
(
p
i
)
=
k
i
=
1
1
−
f
(
p
i
)
.
From (1) we also can derive the following formula:
d
|
n
μ(
d
)
f
(
d
)
=
(
1
−
f
(
p
1
))
· · ·
(
1
−
f
(
p
k
)).
(
2
)

---

6.1. Multiplicative Functions
107
If we take
f
=
1 in formula (2), then we get the following basic property of
the M¨obius function: For any integer
n
≥
2,
d
|
n
μ(
d
)
=
0
.
Theorem 6.1.3.
(M¨obius inversion formula)
Let f be an arithmetic function and
let F be its summation function. Then
f
(
n
)
=
d
|
n
μ(
d
)
F
n
d
.
(
3
)
Proof.
We have
d
|
n
μ(
d
)
F
n
d
=
d
|
n
μ(
d
)
c
|
n
d
f
(
c
)
=
d
|
n
c
|
n
d
μ(
d
)
f
(
c
)
=
c
|
n
d
|
n
c
μ(
d
)
f
(
c
)
=
c
|
n
f
(
c
)
d
|
n
c
μ(
d
)
=
f
(
n
),
since for
n
c
>
1 we have
"
d
|
n
c
μ(
d
)
=
0.
We have used the fact that the sets
)
(
d
,
c
)
d
|
n
and
c
|
n
d
*
and
)
(
d
,
c
)
c
|
n
and
d
|
n
c
*
are equal.
They are both equal to
{
(
c
,
d
)
cd
|
n
}
.
Theorem 6.1.4.
Let f be an arithmetic function and let F be its summation func-
tion. If F is multiplicative, then so is f .
Proof.
Let
m
,
n
be positive integers such that gcd
(
m
,
n
)
=
1 and let
d
be a divisor
of
mn
. Then
d
=
kh
, where
k
|
m
,
h
|
n
, and gcd
(
k
,
h
)
=
1. Applying the M¨obius
inversion formula, it follows that
f
(
mn
)
=
d
|
mn
μ(
d
)
F
mn
d
=
k
|
m
h
|
n
μ(
kh
)
F
mn
kh
=
k
|
m
h
|
n
μ(
k
)μ(
h
)
F
m
k
F
n
h
=
k
|
m
μ(
k
)
F
m
k
h
|
n
μ(
h
)
F
n
h
=
f
(
m
)
f
(
n
).

---

108
I Fundamentals, 6. Arithmetic Functions
Let
f
and
g
be two arithmetic functions. Define their
convolution product
or
Dirichlet
2
product f
∗
g
by
(
f
∗
g
)(
n
)
=
d
|
n
f
(
d
)
g
n
d
.
Note that the convolution product can be written more symmetrically as
(
f
∗
g
)(
n
)
=
ab
=
n
f
(
a
)
g
(
b
).
The following relation holds: 1
∗
f
=
F
, the summation function of
f
.
Problem 6.1.1.
(1) Prove that the convolution product is commutative and asso-
ciative.
(2) Prove that for any arithmetic function f ,
f
∗
ε
=
ε
∗
f
=
f
,
where
ε(
n
)
=
1
if n
=
1
and
0
otherwise.
Solution.
Let
f
and
g
be two arithmetic functions. Then
(
f
∗
g
)(
n
)
=
d
|
n
f
(
d
)
g
n
d
=
d
1
|
n
f
n
d
1
g
(
d
1
)
=
(
g
∗
f
)(
n
),
since if
d
runs through all divisors of, then so does
d
1
=
n
d
. Therefore
f
∗
g
=
g
∗
f
.
Let
f
,
g
,
h
be arithmetic functions. To prove the associativity law, let
u
=
g
∗
h
and consider
f
∗
u
=
f
∗
(
g
∗
h
)
. We have
(
f
∗
u
)(
n
)
=
a
|
n
f
(
a
)
u
n
a
=
ad
=
n
f
(
a
)
bc
=
d
g
(
b
)
h
(
c
)
=
abc
=
n
f
(
a
)
g
(
b
)
h
(
c
).
Similarly, if we set
v
=
f
∗
g
and consider
v
∗
h
, we have
(v
∗
h
)(
n
)
=
dc
=
n
v(
d
)
h
(
c
)
=
dc
=
n
ab
=
d
f
(
a
)
g
(
b
)
h
(
c
)
=
abc
=
n
f
(
a
)
g
(
b
)
h
(
c
)
;
2
Johann Peter Gustav Lejeune Dirichlet (1805–1859), German mathematician who proved in 1837
that there are infinitely many primes in any arithmetic progression of integers for which the common
difference is relatively prime to the terms. Dirichlet made essential contributions in number theory,
probability theory, functional analysis, and Fourier series.

---