|
II Solutions, 6. Arithmetic Functions
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
λ
.
Solution.
(1) Assume
m
=
p
α
1
1
· · ·
p
α
k
k
and
n
=
p
β
1
1
· · ·
p
β
k
k
, where
α
1
, . . . , α
k
,
β
1
, . . . , β
k
≥
0. Then
mn
=
p
α
1
+
β
1
1
· · ·
p
α
k
+
β
k
k
and
λ(
mn
)
=
(
−
1
)
α
1
+
β
1
+···+
α
k
+
β
k
=
(
−
1
)
α
1
+···+
α
k
(
−
1
)
β
1
+···+
β
k
=
λ(
m
)λ(
n
).
(2) Because
λ
is multiplicative, according to Theorem 6.1.2, it follows that its
summation function
also has this property. Therefore, it is sufficient to calculate
for a power of a prime. we have
(
p
α
)
=
(
1
)
+
(
p
)
+ · · · +
(
p
α
)
=
1 if
α
even,
0 if
α
odd.
If
n
=
p
α
1
1
· · ·
p
α
k
k
, then
(
n
)
=
(
p
α
1
1
)
· · ·
(
p
α
k
k
)
=
1 if all
α
1
, . . . , α
k
are
even and 0 otherwise. Hence
(
n
)
=
1 if
n
is a square,
0 otherwise.
(3) Let
g
be the convolutive inverse of
λ
. From Problem 6.1.4(2) it follows
that
g
is multiplicative; hence it is determined by its values on powers of primes.
From
g
∗
λ
=
ε
we get
(
g
∗
λ)(
p
)
=
g
(
1
)λ(
p
)
+
g
(
p
)λ(
1
)
= −
1
+
g
(
p
)
=
0, i.e.,
g
(
p
)
=
1 for any prime
p
. Also,
(
g
∗
λ)(
p
2
)
=
0 implies 1
−
1
+
g
(
p
2
)
=
0, i.e.,
g
(
p
2
)
=
0. A simple inductive argument shows that
g
(
p
α
)
=
0 for any positive
integer
α
≥
2. It follows that
g
(
n
)
=
⎧
⎨
⎩
1 if
n
=
1
,
0 if
p
2
|
n
for some prime
p
>
1
,
1 if
n
=
p
1
· · ·
p
k
,
where
p
1
, . . . ,
p
k
are distinct primes
,
i.e.,
g
=
μ
2
, where
μ
is the M¨obius function. Hence
g
(
n
)
=
1 if
n
is square-free,
and 0 otherwise.
Problem 6.1.8.
Let an integer n
>
1
be factored into primes: n
=
p
α
1
1
· · ·
p
α
m
m
( p
i
distinct) and let its own positive integral exponents be factored similarly. The
process is to be repeated until it terminates with a unique “constellation” of prime
6.2. Number of Divisors
289
numbers. For example, the constellation for
192
is
192
=
2
2
2
·
3
·
3
and for
10000
is
10000
=
2
2
2
·
5
2
. Call an arithmetic function g generally multiplicative if
g
(
ab
)
=
g
(
a
)
g
(
b
)
whenever the constellations for a and b have no prime in
common.
(1) Prove that every multiplicative function is generally multiplicative. Is the
converse true?
(2) Let h be an additive function (i.e., h
(
ab
)
=
h
(
a
)
+
h
(
b
)
whenever
gcd
(
a
,
b
)
=
1
). Call a function k generally additive if k
(
ab
)
=
k
(
a
)
+
k
(
b
)
whenever the constellations for a and b have no prime in common. Prove that
every additive function is generally additive. Is the converse true?
(American Mathematical Monthly)
Solution.
(1) Let
f
be multiplicative. If the constellations for
a
and
b
have no
prime in common, then the same is true of their factorizations, so
f
(
ab
)
=
f
(
a
)
f
(
b
)
. Hence
f
is generally multiplicative.
The converse is not true. Indeed, define
g
(
a
)
to the product of all primes in
the constellation of
a
, taken once only, regardless of how many times they appear
in the constellation. Then
g
is clearly generally multiplicative, but
g
(
9
)
=
6,
g
(
2
)
=
2, and
g
(
18
)
=
6, so
g
(
9
·
2
)
=
g
(
9
)
g
(
2
)
.
(2) The statement “additive implies generally additive” can be proved in the
same way. If
k
(
a
)
is the sum of all primes in the constellation of
a
each taken
once only, then
k
is generally additive, but
k
(
9
)
=
5,
k
(
2
)
=
2, and
k
(
18
)
=
5.
6.2
Number of Divisors
Problem 6.2.5.
Does there exist a positive integer such that the product of its
proper divisors ends with exactly
2001
zeros?
(2001 Russian Mathematical Olympiad)
Solution.
Yes. Given an integer
n
with
τ(
n
)
divisors, the product of its divisors is
;
d
|
n
d
d
|
n
(
n
/
d
)
=
;
d
|
n
d
(
n
/
d
)
=
n
τ(
n
)
.
Thus, the product of all proper positive divisors of
n
equals
n
1
2
τ(
n
)
−
1
.
Since this number ends in exactly 2001 zeros,
1
2
τ(
n
)
−
1 divides 2001. Sup-
pose
1
2
τ(
n
)
−
1
=
2001. Then 10
|
n
but 100
n
and
τ(
n
)
=
4004
=
2
·
2
·
7
·
11
·
13.
One way to arrange this is to take
n
=
2
1
·
5
1
·
7
·
11
10
·
13
12
.
290
II Solutions, 6. Arithmetic Functions
Problem 6.2.6.
Prove that the number of divisors of the form
4
k
+
1
of each
positive integer is not less than the number of its divisors of the form
4
k
+
3
.
Solution.
To solve the problem, consider the function
f
(
n
)
=
⎧
⎨
⎩
0
,
if
n
is even,
1
,
if
n
≡
1
(
mod 4
),
−
1
,
if
n
≡
3
(
mod 4
).
It follows directly from this definition that
f
(
n
)
is multiplicative. Now we ap-
ply (1). The even divisors of
n
do not influence its left-hand side. Each divisor of
the form 4
k
+
1 contributes a 1, and each divisor of the form 4
k
+
3 contributes
a
−
1. Consequently, it suffices to prove that the summation function of
f
,
"
d
|
n
f
(
d
)
is nonnegative for each positive integer
n
.
Take any prime divisor
p
i
of
n
. If
p
i
≡
1
(
mod 4
)
, then the same congruence
holds for all powers of
p
i
, so the
i
th factor in the right-hand side of (1) is positive.
If
p
i
is congruent to 3 modulo 4, then so are its odd powers, while the even powers
are congruent to 1 modulo 4. In this case the
i
th factor in the right-hand side has
the form 1
−
1
+
1
−
1
+ · · ·
, and it equals 1 or 0 according as
α
i
is even or odd.
Summing up, we conclude that the sum in question is nonnegative.
Problem 6.2.7.
Let d
1
,
d
2
, . . . ,
d
l
be all positive divisors of a positive integer. For
each i
=
1
,
2
, . . . ,
l denote by a
i
the number of positive divisors of d
i
. Then
a
3
1
+
a
3
2
+ · · · +
a
3
l
=
(
a
1
+
a
2
+ · · · +
a
l
)
2
.
Solution.
The basic ingredient in the proof is the well-known identity
n
k
=
1
k
3
=
n
(
n
+
1
)
2
2
=
n
k
=
1
k
2
.
We have
a
1
+
a
2
+ · · · +
a
l
=
d
|
n
τ(
d
)
=
k
i
=
1
1
+
τ(
p
i
)
+ · · · +
τ(
p
α
i
i
)
,
a
3
1
+
a
3
2
+ · · · +
a
3
l
=
d
|
n
τ(
d
)
3
=
k
i
=
1
1
+
τ(
p
i
)
3
+ · · · +
τ(
p
α
i
i
)
3
,
where
n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of
n
.
Since
1
+
τ(
p
i
)
+ · · · +
τ(
p
α
i
i
)
=
1
+
2
+ · · · +
(α
i
+
1
)
and
1
+
τ(
p
i
)
3
+· · ·+
τ(
p
α
i
i
)
3
=
1
3
+
2
3
+· · ·+
(α
+
i
+
1
)
3
= [
1
+
2
+· · ·+
(α
+
i
+
1
)
]
2
,
the conclusion follows.
Do'stlaringiz bilan baham: |
