|
II Solutions, 2. Powers of Integers
Problem 2.1.21.
Is it possible to find
100
positive integers not exceeding
25000
such that all pairwise sums of them are different?
(42nd International Mathematical Olympiad Shortlist)
Solution.
Yes. The desired result is an immediate consequence of the following
fact applied to
p
=
101.
Lemma.
For any odd prime number p, there exist p positive integers less than
2
p
2
with all sums distinct.
Proof.
We claim that the numbers
a
n
=
2
np
+
(
n
2
)
p
,
n
=
0
,
1
, . . . ,
p
−
1, have
the desired property, where
(
x
)
p
denotes the remainder of
x
upon division by
p
.
Suppose that
a
k
+
a
l
=
a
m
+
a
n
. By the construction of
a
i
, we have
2
p
(
k
+
l
)
≤
a
k
+
a
l
≤
2
p
(
k
+
l
+
1
).
Hence we must have
k
+
l
=
m
+
n
, and therefore also
(
k
2
)
p
+
(
l
2
)
p
=
(
m
2
)
p
+
(
n
2
)
p
.
Thus
k
+
l
≡
m
+
n
and
k
2
+
l
2
≡
m
2
+
n
2
(
mod
p
).
But then it holds that
(
k
−
l
)
2
=
2
(
k
2
+
l
2
)
−
(
k
+
l
)
2
≡
(
m
−
n
)
2
(
mod
p
),
so
k
−
l
≡ ±
(
m
−
n
)
, which leads to
{
k
,
l
} = {
m
,
n
}
. This proves the lemma.
Problem 2.1.22.
Do there exist
10
distinct integers, the sum of any
9
of which is
a perfect square?
(1999 Russian Mathematical Olympiad)
Solution.
Yes, there do exist 10 such integers. Write
S
=
a
1
+
a
2
+ · · · +
a
10
, and
consider the linear system of equations
S
−
a
1
=
9
·
1
2
S
−
a
2
=
9
·
2
2
. . .
S
−
a
10
=
9
·
10
2
.
Adding all these gives
9
S
=
9
·
(
1
2
+
2
2
+ · · · +
10
2
),
2.1. Perfect Squares
251
so that
a
k
=
S
−
9
k
2
=
1
2
+
2
2
+ · · · +
10
2
−
9
k
2
.
Then all the
a
k
’s are distinct integers, and any nine of them add up to a perfect
square.
Problem 2.1.23.
Let n be a positive integer such that n is a divisor of the sum
1
+
n
−
1
i
=
1
i
n
−
1
.
Prove that n is square-free.
(1995 Indian Mathematical Olympiad)
Solution.
If
n
=
mp
2
for some prime
p
, then
1
+
n
−
1
i
=
1
i
n
−
1
=
1
+
p
−
1
j
=
0
mp
−
1
k
=
0
(
kp
+
j
)
n
−
1
≡
1
+
(
mp
)
p
−
1
j
=
0
j
n
−
1
≡
1
(
mod
p
),
and the sum is not even a multiple of
p
. Hence if the sum is a multiple of
n
,
n
must have no repeated prime divisors, or equivalently no square divisors greater
than 1.
Remark.
The famous Giuga’s conjecture states that if
n
>
1 satisfies
n
|
1
+
"
n
−
1
i
=
1
i
n
−
1
, then
n
is a prime.
The reader can prove instead that for any such
n
we have that for any prime
divisor
p
of
n
,
p
−
1
|
n
p
−
1 and
p
|
n
p
−
1.
Problem 2.1.24.
Let n
,
p be integers such that n
>
1
and p is a prime.
If n
|
(
p
−
1
)
and p
|
(
n
3
−
1
)
, show that
4
p
−
3
is a perfect square.
(2002 Czech–Polish–Slovak Mathematical Competition)
Solution.
From
n
|
p
−
1 it follows
p
−
1
≥
n
and
p
>
n
. Because
p
|
n
3
−
1
=
(
n
−
1
)(
n
2
+
n
+
1
)
we get
p
|
n
2
+
n
+
1, i.e.,
pk
=
n
2
+
n
+
1 for some positive integer
k
.
On the other hand,
n
|
p
−
1 implies
p
≡
1
(
mod
n
)
and
pk
≡
k
(
mod
n
)
.
We obtain
n
2
+
n
+
1
≡
k
(
mod
n
)
; hence
k
≡
1
(
mod
n
)
.
It follows that
p
=
an
+
1,
k
=
bn
+
1 for some integers
a
>
0,
b
≥
0. We
can write
(
an
+
1
)(
bn
+
1
)
=
n
2
+
n
+
1
,
252
II Solutions, 2. Powers of Integers
so
abn
2
+
(
a
+
b
)
n
+
1
=
n
2
+
n
+
1
,
i.e.,
abn
+
(
a
+
b
)
=
n
+
1
.
If
b
≥
1, then
abn
+
(
a
+
b
)
≥
n
+
2
>
n
+
1. So
b
=
0,
k
=
1,
p
=
n
2
+
n
+
1.
Therefore
4
p
−
3
=
4
n
2
+
4
n
+
4
−
3
=
4
n
2
+
4
n
+
1
=
(
2
n
+
1
)
2
.
Problem 2.1.25.
Show that for any positive integer n
>
10000
, there exists a
positive integer m that is a sum of two squares and such that
0
<
m
−
n
<
3
4
√
n.
(Russian Mathematical Olympiad)
Solution.
Suppose
k
2
≤
n
+
1
< (
k
+
1
)
2
and write
n
+
1
=
k
2
+
r
. Then
r
≤
2
k
≤
2
√
n
+
1. Suppose
l
2
<
r
≤
(
l
+
1
)
2
and write
r
=
(
l
+
1
)
2
−
s
. Then
0
≤
s
≤
2
l
<
2
√
r
≤
2
3
/
2
(
n
+
1
)
1
/
4
. Let
m
=
k
2
+
(
l
+
1
)
2
. Then
1
≤
m
−
n
=
s
+
1
<
2
3
/
2
(
n
+
1
)
1
/
4
+
1
.
Thus it remains only to show that for
n
>
10000 we have 2
3
/
2
(
n
+
1
)
1
/
4
+
1
<
3
n
1
/
4
. For this we note that
2
3
/
2
(
n
+
1
)
1
/
4
+
1
n
1
/
4
=
2
3
/
2
(
1
+
1
/
n
)
1
/
4
+
1
/
n
1
/
4
≤
2
3
/
2
(
1
+
1
/
10000
)
1
/
4
+
1
/
10000
1
/
4
≈
2
.
928
<
3
.
Problem 2.1.26.
Show that a positive integer m is a perfect square if and only if
for each positive integer n, at least one of the differences
(
m
+
1
)
2
−
m
, (
m
+
2
)
2
−
m
, . . . , (
m
+
n
)
2
−
m
is divisible by n.
(2002 Czech and Slovak Mathematical Olympiad)
Solution.
First, assume that
m
is a perfect square. If
m
=
a
2
, then
(
m
+
c
)
2
−
m
=
(
m
+
c
)
2
−
a
2
=
(
m
+
c
+
a
)(
m
+
c
−
a
).
Clearly, there exists some
c
, with 1
≤
c
≤
n
, for which
m
+
c
+
a
is divisible
by
n
. Thus, one of the given differences is divisible by
n
if
m
is a perfect square.
Now we assume that
m
is not a perfect square and show that there exists
n
for
which none of the given differences is divisible by
n
. Clearly, there exists a prime
p
and positive integer
k
such that
p
2
k
−
1
is the highest power of
p
that divides
m
.
2.2. Perfect Cubes
253
We may let
m
=
bp
2
k
−
1
, with
b
and
p
being relatively prime. Furthermore, pick
n
=
p
2
k
. For the sake of contradiction, assume that there exists a positive integer
c
for which
(
m
+
c
)
2
−
m
is divisible by
n
. By expanding
(
m
+
c
)
2
−
m
, we note
that
p
2
k
|
2
bcp
2
k
−
1
+
c
2
−
bp
2
k
−
1
.
If
p
2
k
divides the quantity, then so does
p
2
k
−
1
. Thus,
p
2
k
−
1
|
c
2
, and so
p
k
|
c
. Let
c
=
r p
k
. Then, we have
p
2
k
|
2
br p
3
k
−
1
+
r
2
p
2
k
−
bp
2
k
−
1
.
However, this implies that
p
|
b
, which contradicts the original assumption
that
b
and
p
are relatively prime. Therefore, if
m
is not a perfect square,
n
may
be chosen so that none of the given differences are divisible by
n
. This completes
the proof.
Do'stlaringiz bilan baham: |
