|
I Fundamentals, 6. Arithmetic Functions
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
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)
6.2
Number of Divisors
For a positive integer
n
denote by
τ(
n
)
the number of its divisors. It is clear that
τ(
n
)
=
d
|
n
1
,
that is,
τ
is the summation function of the multiplicative function
f
(
m
)
=
1,
m
∈
Z
∗
+
. Applying Theorem 6.1.2, it follows that
τ
is multiplicative.
Theorem 6.2.1.
If n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of n, then
τ(
n
)
=
(α
1
+
1
)
· · ·
(α
k
+
1
).
(
4
)
Proof.
Using the fact that
τ
is multiplicative, we have
τ(
n
)
=
τ(
p
α
1
1
)
· · ·
τ(
p
α
k
k
)
=
(α
1
+
1
)
· · ·
(α
k
+
1
),
because
p
α
i
i
has exactly
α
i
+
1 divisors,
i
=
1
, . . . ,
k
.
Problem 6.2.1.
(1) For any n
≥
1
,
n
m
=
1
τ(
m
)
=
n
k
=
1
#
n
k
$
.
(2) For any n
≥
1
,
τ(
n
)
=
n
k
=
1
#
n
k
$
−
#
n
−
1
k
$
.
6.2. Number of Divisors
113
(3) Prove the formula
1
n
log
n
n
m
=
1
τ(
m
)
=
1
.
Solution.
(1) Note that since
k
is a divisor of exactly
n
/
k
of the numbers
{
1
,
2
, . . .
,
n
}
, we have
n
k
=
1
#
n
k
$
=
n
m
=
1
τ(
m
).
(2) Note that
#
n
k
$
−
#
n
−
1
k
$
=
1 if
k
|
n
,
0 otherwise.
Hence
n
k
=
1
#
n
k
$
−
#
n
−
1
k
$
=
k
|
n
1
=
τ(
n
).
Alternatively, we can derive this formula by taking a difference of the relation
in (1).
(3) Using the inequalities
x
−
1
<
x
≤
x
, from the relation in (1) we get
n
k
=
1
1
k
−
1
<
1
n
n
m
=
1
τ(
m
)
≤
n
k
=
1
1
k
,
i.e.,
n
k
=
1
1
k
−
log
n
+
log
n
−
1
<
1
n
n
m
=
1
τ(
m
)
≤
n
k
=
1
1
k
−
log
n
+
log
n
,
and the formula follows by dividing by log
n
.
Remark.
It is clear that
n
is a prime if and only if
τ(
n
)
=
2. Hence
n
k
=
1
#
n
k
$
−
#
n
−
1
k
$
=
2
if and only if
n
is a prime.
Problem 6.2.2.
Find all positive integers d that have exactly
16
positive integral
divisors d
1
,
d
2
, . . . ,
d
16
such that
1
=
d
1
<
d
2
<
· · ·
<
d
16
=
d
,
d
6
=
18
, and d
9
−
d
8
=
17
.
(1998 Irish Mathematical Olympiad)
114
I Fundamentals, 6. Arithmetic Functions
Solution.
Let
d
=
p
α
1
1
p
α
2
2
· · ·
p
α
m
m
with
p
1
, . . . ,
p
m
distinct primes. Then
d
has
(
a
1
+
1
)(
a
2
+
1
)
· · ·
(
a
m
+
1
)
divisors. Since 18
=
2
·
3
2
, it has 6 divisors: 1, 2, 3, 6,
9, 18. Since
d
has 16 divisors, we know that
d
=
2
·
3
3
p
or
d
=
2
·
3
7
. If
d
=
2
·
3
7
,
then
d
8
=
54,
d
9
=
81, and
d
9
−
d
8
=
17. Thus
d
=
2
·
3
3
p
for some prime
p
>
18. If
p
<
27, then
d
7
=
p
,
d
8
=
27,
d
9
=
2
p
=
27
+
17
+
44
⇒
p
=
22,
a contradiction. Thus
p
>
27. If
p
<
54, then
d
7
=
27,
d
8
=
p
,
d
9
=
54
=
d
8
+
17
⇒
p
=
37. If
p
>
54, then
d
7
=
27,
d
8
=
54,
d
9
=
d
8
+
17
=
71. We
obtain two solutions to the problem: 2
·
3
3
·
37
=
1998 and 2
·
3
3
·
71
=
3834.
Problem 6.2.3.
For how many (a) even and (b) odd numbers n does n divide
3
12
−
1
, yet n does not divide
3
k
−
1
for k
=
1
,
2
, . . . ,
11
?
(1995 Austrian Mathematical Olympiad)
Solution.
We note that
3
12
−
1
=
(
3
6
−
1
)(
3
6
+
1
)
=
(
3
2
−
1
)(
3
4
+
3
2
+
1
)(
3
2
+
1
)(
3
4
−
3
2
+
1
)
=
(
2
3
)(
7
·
13
)(
2
·
5
)(
73
).
Recall that the number of divisors of
p
e
1
1
· · ·
p
e
k
k
is
(
e
1
+
1
)
· · ·
(
e
k
+
1
)
. There-
fore 3
12
−
1 has 2
·
2
·
2
·
2
=
16 odd divisors and 4
·
16
=
64 even divisors.
If 3
12
≡
1
(
mod
m
)
for some integer
m
, then the smallest integer
d
such
that 3
d
≡
1
(
mod
m
)
divides 12. (Otherwise, we could write 12
=
pq
+
r
with 0
<
r
<
d
and obtain 3
r
≡
1
(
mod
m
)
.) Hence to ensure
n
3
k
−
1 for
k
=
1
, . . . ,
11, we need only check
k
=
1
,
2
,
3
,
4
,
6. But
3
1
−
1
=
2
,
3
2
−
1
=
2
3
,
3
3
−
1
=
2
·
13
,
3
4
−
1
=
2
4
·
5
,
3
6
−
1
=
2
3
·
7
·
13
.
The odd divisors we throw out are 1, 5, 7, 13, 91, while the even divisors are
2
i
for 1
≤
i
≤
4, 2
i
·
5 for 1
≤
i
≤
4, and each of 2
j
·
7, 2
j
·
13, and 2
j
·
7
·
13 for
1
≤
i
≤
3. Since we are discarding 17 even divisors and 5 odd ones, we remain
with 47 even divisors and 11 odd ones.
Problem 6.2.4.
Let
τ(
n
)
denote the number of divisors of the natural number n.
Prove that the sequence
τ(
n
2
+
1
)
does not become strictly increasing from any
given point onward.
(1998 St. Petersburg City Mathematical Olympiad)
6.3. Sum of Divisors
115
Solution.
We first note that for
n
even,
τ(
n
2
+
1
)
≤
n
. Indeed, exactly half of the
divisors of
n
2
+
1 are less than
n
, and all are odd, so there are at most 2
(
n
/
2
)
in
all.
Now if
τ(
n
2
+
1
)
becomes strictly increasing for
n
≥
N
, then
τ((
n
+
1
)
2
+
1
)
≥
τ(
n
2
+
1
)
+
2
for
n
≥
N
(since
τ(
k
)
is even for
k
not a perfect square). Thus
τ(
n
2
+
1
)
≥
τ(
N
2
+
1
)
+
2
(
n
−
N
)
, which exceeds
n
for large
N
, contradiction.
Additional Problems
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)
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.
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 divisors of
d
i
. Then
a
3
1
+
a
3
2
+ · · · +
a
3
l
=
(
a
1
+
a
2
+ · · · +
a
l
)
2
.
Do'stlaringiz bilan baham: |
