|
Solution.
There are nine prime numbers less than 26:
p
1
=
2,
p
2
=
3
, . . .
,
p
9
=
23. Any element
x
of
M
has a representation
x
=
9
i
=
1
p
a
i
i
,
a
i
≥
0. If
x
,
y
∈
M
and
y
=
9
i
=
1
p
b
i
i
, the product
x y
=
9
i
=
1
p
a
i
+
b
i
i
is a perfect square if and only
if
a
i
+
b
i
≡
0
(
mod 2
)
. Equivalently,
a
i
≡
b
i
(
mod 2
)
for all
i
=
1
,
2
, . . . ,
9.
Because there are 2
9
=
512 elements in
(
Z
/
2
Z
)
9
, any subset of
M
having at least
513 elements contains two elements
x
,
y
such that
x y
is a perfect square. Starting
from
M
and eliminating such pairs, one obtains
1
2
(
1985
−
513
)
=
736
>
513
distinct two-element subsets of
M
having a square as the product of elements.
Reasoning as above, we find among these squares at least one pair (in fact many
pairs) whose product is a fourth power.
Problem 2.3.4.
Let A be a subset of
{
0
,
1
, . . . ,
1997
}
containing more than 1000
elements. Prove that A contains either a power of
2
, or two distinct integers whose
sum is a power of
2
.
(1997 Irish Mathematical Olympiad)
Solution.
Suppose
A
did not satisfy the conclusion. Then
A
would contain at most
half of the integers from 51 to 1997, since they can be divided into pairs whose
sum is 2048 (with 1024 left over); likewise,
A
contains at most half of the integers
from 14 to 50, at most half of the integers from 3 to 13, and possibly 0, for a total
of
973
+
18
+
5
+
1
=
997
integers.
Problem 2.3.5.
Show that in the arithmetic progression with first term
1
and dif-
ference
729
, there are infinitely many powers of
10
.
(1996 Russian Mathematical Olympiad)
First solution.
We will show that for all natural numbers
n
, 10
81
n
−
1 is divisible
by 729. In fact,
10
81
n
−
1
=
(
10
81
)
n
−
1
n
=
(
10
81
−
1
)
·
A
,
2.3.
k
th Powers of Integers,
k
at least 4
59
and
10
81
−
1
=
9
. . .
9
81
=
(
9
. . .
9
9
)
· · ·
(
10
. . .
01
8
10
. . .
01
8
. . .
10
. . .
01
8
)
=
9
(
1
. . .
1
9
)
· · ·
(
10
. . .
01
8
10
. . .
01
8
. . .
10
. . .
01
8
).
The second and third factors have nine digits equal to 1 and the root of digits (if
any) 0, so the sum of the digits is 9, and each is a multiple of 9. Hence 10
81
−
1 is
divisible by 9
3
=
729, as is 10
81
n
−
1 for any
n
.
Second solution.
In order to prove that 10
81
−
1 is divisible by 9
3
, just write
10
81
−
1
=
(
9
+
1
)
81
−
1
=
k
·
9
3
+
81
2
9
2
+
81
1
·
9
=
k
·
9
3
+
81
·
40
·
9
2
+
81
·
9
=
(
k
+
361
)
·
9
3
.
Remark.
An alternative solution uses Euler’s theorem (see Section 7.2). We have
10
ϕ(
729
)
≡
1
(
mod 729
)
; thus 10
n
ϕ(
729
)
is in this progression for any positive
integer
n
.
Additional Problems
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)
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)
Problem 2.3.8.
Prove that a product of three consecutive integers cannot be a
power of an integer.
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)
Problem 2.3.10.
Prove that there is no infinite arithmetic progression consisting
only of powers
≥
2.
3
Floor Function and Fractional Part
3.1
General Problems
For a real number
x
there is a unique integer
n
such that
n
≤
x
<
n
+
1.
We say that
n
is the
greatest integer less than or equal to x
or the
floor
of
x
.
We write
n
=
x
. The difference
x
−
x
is called the
fractional part
of
x
and is
denoted by
{
x
}
.
The integer
−−
x
is called the
ceiling
of
x
and is denoted by
x
.
Examples.
(1)
2
.
1
=
2,
{
2
.
1
} =
0
.
1, and
2
.
1
=
3.
(2)
−
3
.
9
= −
4,
{−
3
.
9
} =
0
.
1, and
−
3
.
9
= −
3.
The following properties are useful:
(1) If
a
and
b
are integers,
b
>
0, and
q
is the quotient when
a
is divided by
b
, then
q
=
a
b
.
(2) For any real number
x
and any integer
n
,
x
+
n
=
x
+
n
and
x
+
n
=
x
+
n
.
(3) For any positive real number
x
and any positive integer
n
, the number of
positive multiples of
n
not exceeding
x
is
x
n
.
(4) For any real number
x
and any positive integer
n
,
x
n
=
x
n
.
(5) For any real numbers
x
and
y
,
x
+
y
−
1
≤
x
+
y
≤
x
+
y
.
We will prove the last three properties. For (3), consider all multiples
1
·
n
,
2
·
n
, . . . ,
k
·
n
,
where
k
·
n
≤
x
< (
k
+
1
)
n
. That is,
k
≤
x
n
<
k
+
1 and the conclusion
follows. For (4) write
x
=
m
and
{
x
} =
α
. From the division algorithm and
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_3,
61
62
I Fundamentals, 3. Floor Function and Fractional Part
property (1) above it follows that
m
=
n
m
n
+
r
, where 0
≤
r
≤
n
−
1. We
obtain 0
≤
r
+
α
≤
n
−
1
+
α <
n
, that is,
r
+
α
n
=
0 and
#
x
n
$
=
%
m
+
α
n
&
=
%#
m
n
$
+
r
+
α
n
&
=
#
m
n
$
+
%
r
+
α
n
&
=
#
m
n
$
=
%
x
n
&
.
Remark.
An easier proof of (4) may be this:
Since
x
n
≤
x
n
<
x
n
+
1, we can write
x
=
n
x
n
+
s
with 0
≤
x
<
n
. By
(2), we have
x
=
n
x
n
+
s
, so
x
n
=
#
x
n
$
+
s
n
.
Applying (2) again gives
%
x
n
&
=
#
x
n
$
+
%
x
n
&
.
Since 0
≤
x
≤
s
<
n
, 0
≤
s
n
<
1. Hence the last term is zero and we get (4).
For (5) just set
x
=
m
,
{
x
} =
α
, and
y
=
n
,
{
y
} =
β
and reduce the
inequalities to
α
+
β
−
1
≤
0
≤
α
+
β
. Because
α
+
β
is 0 or 1, we are
done.
The following properties connecting the floor and the ceiling of
x
are obvious:
(6) For any real number
x
,
x
−
x
≤
1.
Problem 3.1.1.
Find all positive integers n such that
n
√
111
divides
111
.
Solution.
The positive divisors of 111 are 1, 3, 37, 111. So we have the following
cases:
(1)
n
√
111
=
1 or 1
≤
111
<
2
n
; hence
n
≥
7.
(2)
n
√
111
=
3, or 3
n
≤
111
<
4
n
, so
n
=
4.
(3)
n
√
111
=
37, or 37
n
≤
111
<
38
n
, impossible.
(4)
n
√
111
=
111, or 111
n
≤
111
<
112
n
, and so
n
=
1.
Therefore
n
=
1,
n
=
4, or
n
≥
7.
Problem 3.1.2.
Solve in
R
the equation
x
x
=
1
.
Solution.
By definition,
x
x
=
1
implies
1
≤
x
x
<
2
.
We consider the following cases:
Do'stlaringiz bilan baham: |
