|
6.3
Sum of Divisors
For a positive integer
n
denote by
σ(
n
)
the sum of its divisors. Clearly
σ(
n
)
=
d
|
n
d
,
that is,
σ
is the summation function of the multiplicative function
d
(
m
)
=
m
,
m
∈
Z
∗
+
. Applying Theorem 6.1.2, it follows that
σ
is multiplicative.
Theorem 6.3.1.
If n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of n, then
σ(
n
)
=
p
α
1
+
1
1
−
1
p
1
−
1
· · ·
p
α
k
+
1
k
−
1
p
k
−
1
.
Proof.
Because
σ
is multiplicative, it suffices to compute
σ(
p
α
i
i
)
,
i
=
1
, . . . ,
k
.
The divisors of
p
α
i
i
are 1
,
p
i
, . . . ,
p
α
i
i
; hence
σ(
p
α
i
i
)
=
1
+
p
i
+ · · · +
p
α
i
i
=
p
α
1
+
1
i
−
1
p
i
−
1
,
and the conclusion follows.
116
I Fundamentals, 6. Arithmetic Functions
Problem 6.3.1.
(1) For any n
≥
1
,
n
k
=
1
k
#
n
k
$
=
n
m
=
1
σ(
m
).
(2) For any n
≥
1
,
σ(
n
)
=
n
k
=
1
k
#
n
k
$
−
%
n
−
1
k
&
.
(3) If
lim
n
→∞
"
n
m
=
1
σ(
m
)
n
2
=
a
,
then prove that a
∈
1
2
,
1
.
Solution.
(1) Since
k
is a divisor of exactly
n
/
k
of the numbers
{
1
,
2
, . . . ,
n
}
,
we have
n
k
=
1
k
#
n
k
$
=
n
m
=
1
σ(
m
).
(2) We have
#
n
k
$
−
#
n
−
1
k
$
=
1 if
k
|
n
,
0 otherwise;
hence
n
k
=
1
k
#
n
k
$
−
#
n
−
1
k
$
=
k
|
n
k
=
σ(
n
).
Alternatively, we can apply the formula in (1) for
n
and
n
−
1 and then take
the difference.
(3) Since
x
−
1
<
x
≤
x
, from the relation in (1) we get
n
2
−
n
(
n
+
1
)
2
<
n
m
=
1
σ(
m
)
≤
n
2
,
i.e.,
lim
n
→∞
"
n
m
=
1
σ(
m
)
n
2
∈
1
2
,
1
.
Remarks.
(1) The exact value of this interesting limit is
π
2
/
12.
(2) It is clear that
n
is a prime if and only if
σ(
n
)
=
n
+
1. Hence
n
k
=
1
k
#
n
k
$
−
#
n
−
1
k
$
=
n
+
1
if and only if
n
is a prime.
6.3. Sum of Divisors
117
Problem 6.3.2.
If n is a composite positive integer, then
σ (
n
)
≥
n
+
√
n
+
1
.
Solution.
The integer
n
has a divisor
d
such that
d
=
1 and
d
≤
√
n
. Because
n
d
is also a divisor of
n
, it follows that
n
d
≥
√
n
, and therefore
σ(
n
)
=
k
|
n
k
≥
1
+
n
+
n
d
≥
n
+
√
n
+
1
.
Problem 6.3.3.
For any n
≥
7
,
σ(
n
) <
n
ln
n
.
Solution.
Let
d
1
,
d
2
, . . . ,
d
k
be all the divisors of
n
. They can be also written as
n
d
1
,
n
d
2
, . . . ,
n
d
k
;
hence
σ (
n
)
=
n
1
d
1
+
1
d
2
+ · · · +
1
d
k
≤
n
1
+
1
2
+ · · · +
1
k
,
where
k
=
τ(
n
)
. Inducting on
k
, we prove that for any
k
≥
2,
1
+
1
2
+ · · · +
1
k
<
0
.
81
+
ln
k
.
Now we use the inequality
τ(
n
)
≤
2
√
n
,
n
≥
1. In order to prove it, let us
consider
d
1
<
d
2
<
· · ·
<
d
k
, the divisors of
n
not exceeding
√
n
. The other
divisors are
n
/
d
1
,
n
/
d
2
, . . . ,
n
/
d
k
. We get
τ(
n
)
≤
2
k
≤
2
√
n
.
Using the inequality
τ(
n
)
≤
2
√
n
, it follows that
1
+
1
2
+ · · · +
1
k
<
0
.
81
+
ln
(
2
√
n
) <
1
.
51
+
1
2
ln
n
.
For
n
≥
21 we have ln
n
>
1
.
51
+
1
2
ln
n
, and checking directly the desired
inequality for
n
=
7
, . . . ,
20, the conclusion follows.
Problem 6.3.4.
For any n
≥
1
,
σ (
n
)
τ(
n
)
≥
√
n
.
Solution.
Let
d
1
,
d
2
, . . . ,
d
τ(
n
)
be the divisors of
n
. They can be rewritten as
n
d
1
,
n
d
2
, . . . ,
n
d
τ(
n
)
.
118
I Fundamentals, 6. Arithmetic Functions
Hence
σ (
n
)
2
=
n
(
d
1
+
d
2
+ · · · +
d
τ(
n
)
)
1
d
1
+
1
d
2
+ · · · +
1
d
τ(
n
)
≥
n
τ(
n
)
2
,
and the conclusion follows because of the AM–HM inequality.
Remarks.
(1) This means the average of divisors of
n
is at least
√
n
.
(2) An alternative way to prove this inequality is the following: We start by
noting that for any divisor
d
of
n
we have
d
+
n
d
≥
2
√
n
. This follows from the
AM–GM inequality or is an easy calculus exercise. Then sum this result over all
divisors
d
of
n
, noting that
n
d
also varies over all divisors to get 2
σ(
1
)
≥
2
√
n
τ(
n
)
.
Additional Problems
Problem 6.3.5.
For any
n
≥
2,
σ(
n
) <
n
2
τ(
n
).
(1999 Belarusian Mathematical Olympiad)
Problem 6.3.6.
Find all the four-digit numbers whose prime factorization has the
property that the sum of the prime factors is equal to the sum of the exponents.
Problem 6.3.7.
Let
m
,
n
,
k
be positive integers with
n
>
1. Show that
σ (
n
)
k
=
n
m
.
(2001 St. Petersburg City Mathematical Olympiad)
6.4
Euler’s Totient Function
For any positive integer
n
we denote by
ϕ(
n
)
the number of integers
m
such that
m
≤
n
and gcd
(
m
,
n
)
=
1. The arithmetic function
ϕ
is called
Euler’s
3
totient
function
. It is clear that
ϕ(
1
)
=
1 and for any prime
p
,
ϕ(
p
)
=
p
−
1. Moreover,
if
n
is a positive integer such that
ϕ(
n
)
=
n
−
1 then
n
is a prime.
Theorem 6.4.1.
(Gauss)
For any positive integer n,
d
|
n
ϕ(
d
)
=
n
.
3
Leonhard Euler (1707–1783), Swiss mathematician who worked at the Petersburg Academy and
Berlin Academy of Science. Euler was one of the most prolific mathematicians of all time. Euler
systematized mathematics by introducing the symbols
e
and
i
, and
f
(
x
)
for a function of
x
. He also
made major contributions in optics, mechanics, electricity, and magnetism. Euler did important work
in number theory, proving that the divergence of the harmonic series implies an infinite number of
primes, factoring the fifth Fermat number, and introducing the totient function
ϕ
.
6.4. Euler’s Totient Function
119
Proof.
Let
d
1
,
d
2
, . . . ,
d
k
be the divisors of
n
and let
S
i
= {
m
|
m
≤
n
and
gcd
(
m
,
n
)
=
d
i
}
,
i
=
1
, . . . ,
k
. If
m
∈
S
i
, then
m
=
d
i
m
, where gcd
m
,
n
d
i
=
1. Because
m
≤
n
d
i
, from the definition of
ϕ
it follows that
|
S
i
| =
ϕ
n
d
i
. The sets
S
1
, . . . ,
S
k
give a partition of
{
1
,
2
, . . . ,
n
}
; hence
k
i
=
1
ϕ
n
d
i
=
k
i
=
1
|
S
i
| =
n
.
But
+
n
d
1
, . . . ,
n
d
k
,
= {
d
1
, . . . ,
d
k
}
, so
"
d
|
n
ϕ(
d
)
=
n
.
Theorem 6.4.2.
The function
ϕ
is multiplicative.
Proof.
From Theorem 6.4.1 we obtain that the summation function of
ϕ
is
F
(
n
)
=
n
, which is multiplicative.
The conclusion now follows from Theorem 6.1.4.
Theorem 6.4.3.
If n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of n
>
1
, then
ϕ(
n
)
=
n
1
−
1
p
1
· · ·
1
−
1
p
k
.
Proof.
We first notice that for any prime
p
and for any positive integer
α
,
ϕ(
p
α
)
=
p
α
−
p
α
−
1
=
p
α
1
−
1
p
.
Indeed, the number of all positive integers not exceeding
n
that are divisible
by
p
is
p
α
−
1
; hence
ϕ(
p
α
)
=
p
α
−
p
α
−
1
.
Using Theorem 6.4.3 we have
ϕ(
n
)
=
ϕ(
p
α
1
1
· · ·
p
α
k
k
)
=
ϕ(
p
α
1
1
)
· · ·
ϕ(
p
α
k
k
)
=
p
α
1
1
1
−
1
p
1
· · ·
p
α
k
k
1
−
1
p
k
=
p
α
1
1
· · ·
p
α
k
k
1
−
1
p
1
· · ·
1
−
1
p
k
=
n
1
−
1
p
1
· · ·
1
−
1
p
k
.
Alternative proof.
We employ the inclusion–exclusion principle. Let
T
i
= {
d
|
d
≤
n
and
p
i
|
d
}
,
i
=
1
, . . . ,
k
.
It follows that
T
1
∪ · · · ∪
T
k
= {
m
|
m
≤
n
and gcd
(
m
,
n
) >
1
}
.
120
Do'stlaringiz bilan baham: |
