|
6.1. Multiplicative Functions
109
hence
f
∗
(
g
∗
h
)
=
(
f
∗
g
)
∗
h
.
(2) We have
(ε
∗
f
)(
n
)
=
d
|
n
ε(
d
)
f
n
d
=
f
(
n
),
and we get
ε
∗
f
=
f
∗
ε
=
f
.
Problem 6.1.2.
Let f be an arithmetic function. If f
(
1
)
=
0
, then there is a
unique arithmetic function g such that
f
∗
g
=
ε.
Solution.
We show by induction on
n
that
(
f
∗
g
)(
n
)
=
ε(
n
)
has a unique solution
g
(
1
), . . . ,
g
(
n
)
.
For
n
=
1, we have
f
(
1
)
g
(
1
)
=
1; hence
g
(
1
)
=
1
/
f
(
1
)
.
Suppose
n
>
1 and assume that
g
(
1
), . . . ,
g
(
n
−
1
)
have been uniquely deter-
mined such that
(
f
∗
g
)(
k
)
=
ε(
k
)
holds for
k
=
1
,
2
, . . . ,
n
−
1. Then
f
(
1
)
g
(
n
)
+
d
|
n
d
>
1
f
(
d
)
g
n
d
=
0
,
and we get
g
(
n
)
= −
1
f
(
1
)
d
|
n
d
>
1
f
(
d
)
g
n
d
i.e., the function
g
exists and is unique.
Remark.
The unique function
g
satisfying
f
∗
g
=
ε
, where
f
(
1
)
=
0, is called
the
convolution inverse
of
f
. It is not difficult to show that
μ
is the convolution
inverse to the constant function 1.
Problem 6.1.3.
If f and g are multiplicative, so is their convolution product.
Solution.
Let
h
=
f
∗
g
. We have
h
(
mn
)
=
c
|
mn
f
(
c
)
g
mn
c
.
Set
c
=
ab
, where
a
|
m
and
b
|
n
. Since gcd
(
m
,
n
)
=
1, we can write
c
uniquely in this way. Hence we have
h
(
mn
)
=
a
|
m
b
|
n
f
(
ab
)
g
m
a
n
b
=
a
|
m
f
(
a
)
g
m
a
b
|
n
f
(
b
)
g
n
b
=
h
(
m
)
h
(
n
).
110
I Fundamentals, 6. Arithmetic Functions
Problem 6.1.4.
(1) If both g and f
∗
g are multiplicative, then f is also multi-
plicative.
(2) If g is multiplicative, then so is its convolution inverse.
Solution.
(1) Suppose
f
is not multiplicative. Let
h
=
f
∗
g
. Since
f
is not mul-
tiplicative, there exist
m
and
n
, gcd
(
m
,
n
)
=
1, such that
f
(
mn
)
=
f
(
m
)
f
(
n
)
.
We choose
mn
as small as possible. If
mn
=
1, then we get
f
(
1
)
=
f
(
1
)
f
(
1
)
,
so
f
(
1
)
=
1. Since
h
(
1
)
=
f
(
1
)
g
(
1
)
=
f
(
1
)
=
1,
h
is not multiplicative, a
contradiction. If
mn
>
1, we have
f
(
ab
)
=
f
(
a
)
f
(
b
)
for all
ab
<
mn
with
gcd
(
a
,
b
)
=
1. Now
h
(
mn
)
=
f
(
mn
)
g
(
1
)
+
a
|
m
b
|
n
f
(
ab
)
g
mn
ab
=
f
(
mn
)
+
a
|
m
b
|
n
ab
<
mn
f
(
a
)
f
(
b
)
g
m
a
g
n
b
=
f
(
mn
)
−
f
(
m
)
f
(
n
)
+
h
(
m
)
h
(
n
).
Since
f
(
mn
)
=
f
(
m
)
f
(
n
)
, we have
h
(
mn
)
=
h
(
m
)
h
(
n
)
. Therefore,
h
is not
multiplicative, a contradiction.
(2) Denote by
g
−
1
the convolution inverse of
g
. Then
ε
=
g
∗
g
−
1
=
g
−
1
∗
g
and
g
are both multiplicative. From the previous result it follows that
g
−
1
is
multiplicative.
Problem 6.1.5.
Let f be an arithmetic function that is not identically zero. Prove
that it is completely multiplicative if and only if f
∗
f
=
f
τ
, where
τ(
n
)
is the
number of divisors of n.
(American Mathematical Monthly)
Solution.
If
f
is completely multiplicative, we have
(
f
∗
f
)(
n
)
=
d
|
n
f
(
d
)
f
n
d
=
d
|
n
f
d
n
d
=
d
|
n
f
(
n
)
=
f
(
n
)
d
|
n
1
=
f
(
n
)τ(
n
)
=
(
f
τ)(
n
),
and the relation follows.
Conversely, take
n
=
1. We get
f
2
(
1
)
=
f
(
1
)τ(
1
)
=
f
(
1
)
. It follows that
f
(
1
)
=
0 or
f
(
1
)
=
1. Now suppose that
n
≥
2 and let
n
=
p
α
1
1
· · ·
p
α
k
k
be the
prime factorization of
n
. Put
α(
n
)
=
α
1
+ · · · +
α
k
. It suffices to show that for any
positive integer
n
≥
2, the following relation holds:
f
(
n
)
=
f
(
1
)
f
(
p
1
)
α
1
· · ·
f
(
p
k
)
α
k
.
6.1. Multiplicative Functions
111
We proceed by induction on
α
. If
α(
n
)
=
1, then
n
is a prime, say
n
=
p
, and
the property follows from the fact that
2
f
(
p
)
=
τ(
p
)
f
(
p
)
=
(
f
∗
f
)(
p
)
=
f
(
1
)
f
(
p
)
+
f
(
p
)
f
(
1
)
=
2
f
(
1
)
f
(
p
).
Suppose then that the property holds for all
n
with
α(
n
)
≤
k
. Take any
n
with
α(
n
)
=
k
+
1. Then
τ(
n
)
f
(
n
)
=
2
f
(
1
)
f
(
n
)
+
f
(
a
)
f
(
b
),
where the sum runs over all
a
,
b
with
ab
=
n
and 1
<
a
,
b
<
n
. It follows that
α(
a
)
≤
k
,
α(
b
)
≤
k
, and from the inductive assumption we get
τ(
n
)
f
(
n
)
=
2
f
(
1
)
f
(
n
)
+
(τ(
n
)
−
2
)
{
f
2
(
1
)
f
(
p
1
)
α
1
· · ·
f
(
p
k
)
α
k
}
.
Since
n
is not a prime, certainly
τ(
n
) >
2, and so for both
f
(
1
)
=
0 and
f
(
1
)
=
1, the desired result follows.
Additional Problems
Problem 6.1.6.
Let
f
be a function from the positive integers to the integers
satisfying
f
(
m
+
n
)
≡
f
(
n
) (
mod
m
)
for all
m
,
n
≥
1 (e.g., a polynomial with
integer coefficients). Let
g
(
n
)
be the number of values (including repetitions) of
f
(
1
),
f
(
2
), . . . ,
f
(
n
)
divisible by
n
, and let
h
(
n
)
be the number of these values
relatively prime to
n
. Show that
g
and
h
are multiplicative functions related by
h
(
n
)
=
n
d
|
n
μ(
d
)
g
(
d
)
d
=
n
k
j
=
1
1
−
g
(
p
j
)
p
j
,
where
n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of
n
.
(American Mathematical Monthly)
Problem 6.1.7.
Define
λ(
1
)
=
1, and if
n
=
p
α
1
1
· · ·
p
α
k
k
, define
λ(
n
)
=
(
−
1
)
α
1
+···+
α
k
.
(1) Show that
λ
is completely multiplicative.
(2) Prove that
d
|
n
λ(
d
)
=
1 if
n
is a square,
0 otherwise.
(3) Find the convolutive inverse of
λ
.
112
Do'stlaringiz bilan baham: |
