|
6.3. Sum of Divisors
291
For example, if
n
=
12 we have
d
1
=
1,
d
2
=
2,
d
3
=
3,
d
4
=
4,
d
5
=
6,
d
6
=
12;
a
1
=
1,
a
2
=
2,
a
3
=
2,
a
4
=
3,
a
5
=
4,
a
6
=
6, and
1
3
+
2
3
+
2
3
+
3
3
+
4
3
+
6
3
=
324
=
(
1
+
2
+
2
+
3
+
4
+
6
)
2
.
Remark.
The above identity shows that solving the equation
(
x
1
+
x
2
+ · · · +
x
n
)
2
=
x
3
1
+
x
3
2
+ · · · +
x
3
n
in positive integers is a very difficult job. If we assume that
x
i
=
x
j
for
i
=
j
,
there are only a few solutions. Try to prove this last assertion.
6.3
Sum of Divisors
Problem 6.3.5.
For any n
≥
2
,
σ (
n
) <
n
2
τ(
n
).
(1999 Belarusian Mathematical Olympiad)
Solution.
Let
d
1
,
d
2
, . . . ,
d
τ(
n
)
be the divisors of
n
. They can be rewritten in the
form
n
d
1
,
n
d
2
, . . . ,
n
d
τ(
n
)
.
By the power mean inequality,
σ (
n
)
≤
<
=
=
>
τ(
n
)
τ(
n
)
i
=
1
d
2
i
.
Now,
1
n
2
τ(
n
)
i
=
1
d
2
i
=
τ(
n
)
i
=
1
1
d
2
i
≤
τ(
n
)
j
=
1
1
j
2
<
∞
j
=
1
1
j
2
=
π
2
6
.
Hence
σ(
n
)
≤
<
=
=
>
τ(
n
)
τ(
n
)
i
=
1
d
i
<
;
τ(
n
)
n
2
π
2
6
<
n
2
τ(
n
).
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.
292
II Solutions, 6. Arithmetic Functions
Solution.
(1) If the number has at least four prime divisors, then
n
≥
2
14
·
3
·
5
·
7
>
9999, a contradiction.
(2) If
n
has three prime divisors, these must be 2, 3, and 5. The numbers are
2
8
·
3
·
5
=
3840
,
2
7
·
3
2
·
5
=
5760
,
2
6
·
3
3
·
5
=
8640
,
and 2
7
·
3
·
5
2
=
9600
.
(3) If
n
has 2 prime divisors, at least one of them must be 2, since if neither
is 2, they are at least 3 and 5 and hence
n
≥
3
7
·
5
=
10935 has more than four
digits. The numbers
2
4
·
5
3
=
2000
,
2
3
·
5
4
=
5000
,
2
8
·
7
=
1792
,
2
7
·
7
2
=
6272
satisfy the solutions.
(4) If
n
has only one prime factor, then 5
5
=
3125.
Therefore there are nine solutions.
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)
Solution.
Let
n
=
p
e
1
1
p
e
2
2
· · ·
p
e
k
k
. Because
σ (
n
) >
n
, if
σ(
n
)
k
=
n
m
, then
σ (
n
)
=
p
f
1
1
p
f
2
2
· · ·
p
f
k
k
where
f
i
>
e
i
. This implies
f
i
≥
e
i
+
1, for all
i
, and
σ (
n
)
≥
p
1
+
e
1
1
p
1
+
e
2
2
· · ·
p
1
+
e
k
k
>
p
1
+
e
1
1
−
1
p
1
−
1
p
1
+
e
2
2
−
1
p
2
−
1
· · ·
p
1
+
e
k
k
−
1
p
k
−
1
=
(
1
+
p
1
+ · · · +
p
e
1
1
)(
1
+
p
2
+ · · · +
p
e
2
2
)
· · ·
(
1
+
p
k
+ · · · +
p
e
k
k
)
=
σ (
n
).
This is a contradiction.
6.4
Euler’s Totient Function
Problem 6.4.5.
For a positive integer n, let
ψ(
n
)
be the number of prime factors
of n. Show that if
ϕ(
n
)
divides n
−
1
and
ψ(
n
)
≤
3
, then n is prime.
(1998 Korean Mathematical Olympiad)
Solution.
Note that for prime
p
, if
p
2
|
n
then
p
|
ϕ(
n
)
but
p
n
−
1, contradic-
tion. So we need only show that
n
=
pq
,
n
=
pqr
for primes
p
<
q
<
r
.
First assume
n
=
pq
, so
(
p
−
1
)(
q
−
1
)
|
pq
−
1. Note that
q
≥
3 implies
that the left side is even, so the right is too and
p
,
q
are odd. But if
p
=
3,
q
=
5
then
pq
−
1
(
p
−
1
)(
q
−
1
)
<
2
;
6.4. Euler’s Totient Function
293
the left side is decreasing in each variable and is always greater than 1, so it cannot
be an integer, contradiction.
Now let
n
=
pqr
. As before,
p
,
q
,
r
are odd; if
p
=
3,
q
=
7, and
r
=
11
then
pqr
−
1
(
p
−
1
)(
q
−
1
)(
r
−
1
)
<
2
and again the left side is decreasing and greater than 1; this eliminates all cases
except where
p
=
3,
q
=
5. Then for
r
=
7 we have
pqr
−
1
(
p
−
1
)(
q
−
1
)(
r
−
1
)
<
3
,
so the only integer value ever attainable is 2. Note that
(
15
r
−
1
)/
8
(
r
−
1
)
=
2
gives
r
=
15, which is not a prime, and we have eliminated all cases.
Remarks.
(1) The problem is a direct consequence of Problem 1.1.16.
(2) A long standing conjecture due to Lehmer asserts that if
ϕ(
n
)
|
n
−
1, then
n
is a prime. This has been proved so far for
ψ(
n
)
≤
14. The proofs are very long
and computational and no further progress has been made on this conjecture.
Problem 6.4.6.
Show that the equation
ϕ(
n
)
=
τ(
n
)
has only the solutions n
=
1
,
3
,
8
,
10
,
18
,
24
,
30
.
Solution.
We check directly that the listed integers satisfy the equation and there
are no others
≤
30 with this property. We will prove that for
n
≥
31,
ϕ(
n
) > τ(
n
)
.
For this we consider the multiplicative function
f
(
n
)
=
ϕ(
n
)/τ(
n
)
. If
n
is a
prime, we have
f
(
n
)
=
n
−
1
2
; hence
f
increases on the set of primes.
For a prime
p
, define
S
p
= {
p
α
|
α
≥
1
}
. Because
f
(
p
α
)
=
p
α
−
1
(
p
−
1
)
α
+
1
and
p
α
+
2
≥
2
α
+
2
>
1
α
+
1
,
we obtain
f
(
p
α
+
1
) >
f
(
p
α
)
, that is,
f
increases on
S
p
. Using the fact that
min
p
,α
f
(
p
α
)
=
f
(
2
)
=
1
2
, it follows that in order to solve the given equation we
need to consider the integers
p
α
with
f
(
p
α
)
≤
2. These are 2, 3, 4, 5, 8, 9, 16,
with
f
(
2
)
=
1
2
,
f
(
3
)
=
2
3
,
f
(
3
)
=
f
(
8
)
=
1 and
f
(
5
)
=
f
(
9
)
=
f
(
16
)
=
2.
The only way to write 1 as a product of these values of
f
is to use only ones or a
single
1
2
, a single 2, and possibly some 1’s. These gives the possibilities
n
=
1, 3,
8, 3
·
8
=
24, and
n
=
2
·
5
=
10, 2
·
9
=
18, 2
·
3
·
5
=
30, respectively. Thus
these are exactly the values given in the statement.
Problem 6.4.7.
Let n
>
6
be an integer and let a
1
,
a
2
, . . . ,
a
k
be all positive
integers less than n and relatively prime to n. If
a
2
−
a
1
=
a
3
−
a
2
= · · · =
a
k
−
a
k
−
1
>
0
,
prove that n must be either a prime number or a power of
2
.
(32nd International Mathematical Olympiad)
294
Do'stlaringiz bilan baham: |
