|
II Solutions, 2. Powers of Integers
2.3
k
th Powers of Integers,
k
at least 4
Problem 2.3.6.
Let p be a prime number and a
,
n positive integers. Prove that if
2
p
+
3
p
=
a
n
,
then n
=
1
.
(1996 Irish Mathematical Olympiad)
Solution.
If
p
=
2, we have 2
2
+
3
2
=
13 and
n
=
1. If
p
>
2, then
p
is odd,
so 5 divides 2
p
+
3
p
and so 5 divides
a
. Now if
n
>
1, then 25 divides
a
n
and 5
divides
2
p
+
3
p
2
+
3
=
2
p
−
1
−
2
p
−
2
·
3
+ · · · +
3
p
−
1
≡
p
2
p
−
1
(
mod 5
),
a contradiction if
p
=
5. Finally, if
p
=
5, then 2
5
+
3
5
=
375 is not a perfect
power, so
n
=
1 again.
Problem 2.3.7.
Let x
,
y
,
p
,
n
,
k be natural numbers such that
x
n
+
y
n
=
p
k
.
Prove that if n
>
1
is odd, and p is an odd prime, then n is a power of p.
(1996 Russian Mathematical Olympiad)
Solution.
Let
m
=
gcd
(
x
,
y
)
. Then
x
=
mx
1
,
y
=
my
1
, and by virtue of the given
equation,
m
n
(
x
n
1
+
y
n
1
)
=
p
k
, and so
m
=
p
α
for some nonnegative integer
α
. It
follows that
x
n
1
+
y
n
1
=
p
k
−
n
α
.
(
1
)
Since
n
is odd,
x
n
1
+
y
n
1
x
1
+
y
1
=
x
n
−
1
1
−
x
n
−
2
1
y
1
+
x
n
−
3
1
y
2
1
− · · · −
x
1
y
n
−
2
1
+
y
n
−
1
1
.
(
2
)
Let
A
denote the right side of equation (2). By the condition
p
>
2, it follows
that at least one of
x
1
,
y
1
is greater than 1, so since
n
>
1,
A
>
1.
From (1) it follows that
A
(
x
1
+
y
1
)
=
p
k
−
n
α
, so since
x
1
+
y
1
>
1 and
A
>
1, both of these numbers are divisible by
p
; moreover,
x
1
+
y
1
=
p
β
for
some natural number
β
. Thus
A
=
x
n
−
1
1
−
x
n
−
2
1
(
p
β
−
x
1
)
+ · · · −
x
1
(
p
β
−
x
1
)
n
−
2
+
(
p
β
−
x
1
)
n
−
1
=
nx
n
−
1
1
+
Bp
.
2.3.
k
th Powers of Integers,
k
at least 4
257
Since
A
is divisible by
p
and
x
1
is relatively prime to
p
, it follows that
n
is
divisible by
p
.
Let
n
=
pq
. Then
x
pq
+
y
pq
=
p
k
or
(
x
p
)
q
+
(
y
p
)
q
=
p
k
. If
q
>
1, then by
the same argument,
p
divides
q
. If
q
=
1, then
n
=
p
. Repeating this argument,
we deduce that
n
=
p
l
for some natural number
l
.
Problem 2.3.8.
Prove that a product of three consecutive integers cannot be a
power of an integer.
Solution.
Let
n
be an integer and assume by contradiction that
n
(
n
+
1
)(
n
+
2
)
=
x
z
for some integers
x
and
z
, where
z
≥
2. We note that
n
(
n
+
2
)
=
(
n
+
1
)
2
−
1
and that
n
+
1 and
(
n
+
1
)
2
−
1 are relatively prime. It follows that
n
+
1
=
a
z
,
(
n
+
1
)
2
−
1
=
b
z
,
for some integers
a
and
b
. It follows that
a
2
z
−
b
z
=
1, i.e.,
(
a
2
−
b
)((
a
2
)
z
−
1
+
(
a
2
)
z
−
2
b
+ · · · +
b
z
−
1
)
=
1
.
We get
a
2
−
b
=
1; hence
a
2
=
b
+
1. The equation
(
b
+
1
)
z
−
b
z
=
1 has
the unique solution
z
=
1, a contradiction.
Remark.
A famous theorem of Erd˝os and Selfridge, answering a conjecture of
more than 150 years, states that the product of consecutive integers is never a
power.
Problem 2.3.9.
Show that there exists an infinite set A of positive integers such
that for any finite nonempty subset B
⊂
A,
"
x
∈
B
x is not a perfect power.
(Kvant)
Solution.
The set
A
= {
2
n
3
n
+
1
:
n
≥
1
}
has the desired property. Indeed, if
B
= {
2
n
1
3
n
1
+
1
, . . . ,
2
n
k
n
k
+
1
}
is a finite subset
of
A
, where
n
1
<
· · ·
<
n
k
, then
x
∈
B
x
=
2
n
1
3
n
1
+
1
(
1
+
2
n
2
−
n
1
3
n
2
−
n
1
+ · · · +
2
n
k
−
n
1
3
n
k
−
n
1
)
=
2
n
1
3
n
1
+
1
N
,
where gcd
(
N
,
2
)
=
gcd
(
N
,
3
)
=
1. Taking into account that
n
1
and
n
1
+
1 are
relatively prime, it follows that
"
x
∈
B
x
is not a perfect power.
Problem 2.3.10.
Prove that there is no infinite arithmetic progression consisting
only of perfect powers.
258
II Solutions, 2. Powers of Integers
Solution.
Assume that we have such an arithmetic progression,
an
+
b
,
n
=
1
,
2
, . . .
. It is well known that
n
≥
1
1
an
+
b
= ∞
.
(
1
)
But on the other hand, we have
n
≥
1
1
an
+
b
≤
m
,
s
≥
2
1
m
s
<
+∞
,
contradicting (1).
Remark.
There are alternative solutions to Problems 2.3.9 and 2.3.10 using the
following observation, which is a nice result in its own right.
Lemma.
There are arbitrarily long stretches of consecutive positive integers
that contain no perfect powers.
Proof.
This follows immediately from our observation that
"
m
,
s
≥
2
1
m
s
con-
verges, or more elementarily by the Chinese remainder theorem by finding an
n
with
n
≡
2
(
mod 4
)
,
n
+
1
≡
3
(
mod 9
)
, etc., or with a little analysis by show-
ing that if
p
(
N
)
is the number of perfect powers less than
N
then
lim
N
→∞
p
(
N
)/
N
=
0.
From this Problem 2.3.10 is obvious: there will be infinitely many of these
stretches longer than the difference of the arithmetic progression and hence the
progression cannot cross them. For Problem 2.3.9, we build
A
inductively. Then
the
n
th element
a
n
of
A
is chosen to be the first element of a stretch of 1
+
"
n
−
1
k
=
1
a
k
consecutive elements with no perfect power.
3
Floor Function and Fractional Part
3.1
General Problems
Problem 3.1.10.
Let n be a positive integer. Find with proof a closed formula for
the sum
%
n
+
1
2
&
+
%
n
+
2
2
2
&
+ · · · +
%
n
+
2
k
2
k
+
1
&
+ · · ·
.
(10th International Mathematical Olympiad)
Solution.
The sum is
n
. We rewrite the sum as
%
n
2
+
1
2
&
+
%
n
2
2
+
1
2
&
+ · · · +
%
n
2
k
+
1
+
1
2
&
+ · · ·
,
and use a special case of Hermite’s identity:
%
x
+
1
2
&
=
2
x
−
x
.
This allows us to write the sum as
n
−
#
n
2
$
+
#
n
2
$
−
#
n
2
2
$
+ · · · +
#
n
2
k
$
−
#
n
2
k
+
1
$
+ · · ·
.
The sum telescopes, and
n
/
2
k
+
1
=
0 for large enough
k
’s.
Problem 3.1.11.
Compute the sum
0
≤
i
<
j
≤
n
%
x
+
i
j
&
,
where x is a real number.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
259
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_14,
260
Do'stlaringiz bilan baham: |
