|
II Solutions, 1. Divisibility
Problem 1.5.13.
Find the greatest common divisor of the numbers
A
n
=
2
3
n
+
3
6
n
+
2
+
5
6
n
+
2
when n
=
0
,
1
, . . . ,
1999
.
(1999 Junior Balkan Mathematical Olympiad)
Solution.
We have
A
0
=
1
+
9
+
25
=
35
=
5
·
7
.
Using congruence mod 5, it follows that
A
n
≡
2
3
n
+
3
6
n
+
2
≡
2
3
n
+
9
3
n
+
1
≡
2
3
n
+
(
−
1
)
3
n
+
1
(
mod 5
).
For
n
=
1,
A
1
≡
9
=
0
(
mod 5
)
; hence 5 is not a common divisor.
On the other hand,
A
n
=
8
n
+
9
·
9
3
n
+
25
·
25
3
n
≡
1
+
2
·
2
3
n
+
4
·
4
3
n
≡
1
+
2
·
8
n
+
4
·
64
n
≡
1
+
2
·
1
n
+
4
·
1
n
≡
0
(
mod 7
).
Therefore 7 divides
A
n
for all integers
n
≥
0.
Consequently, the greatest common divisor of the numbers
A
0
,
A
1
, . . .
,
A
1999
is equal to 7.
1.6
Chinese Remainder Theorem
Problem 1.6.3.
Let P
(
x
)
be a polynomial with integer coefficients. Suppose that
the integers a
1
,
a
2
, . . . ,
a
n
have the following property: For any integer x there
exists an i
∈ {
1
,
2
, . . . ,
n
}
such that P
(
x
)
is divisible by a
i
. Prove that there is an
i
0
∈ {
1
,
2
, . . . ,
n
}
such that a
i
0
divides P
(
x
)
for any integer x.
(St. Petersburg City Mathematical Olympiad)
Solution.
Suppose that the claim is false. Then for each
i
=
1
,
2
, . . . ,
n
there
exists an integer
x
i
such that
P
(
x
i
)
is not divisible by
a
i
. Hence, there is a
prime power
p
k
i
i
that divides
a
i
and does not divide
P
(
x
i
)
. Some of the pow-
ers
p
k
1
1
,
p
k
2
2
, . . . ,
p
k
n
n
may have the same base. If so, ignore all but the one with
the least exponent. To simplify notation, assume that the sequence obtained this
way is
p
k
1
1
,
p
k
2
2
, . . . ,
p
k
m
m
,
m
≤
n
(
p
1
,
p
2
, . . . ,
p
m
are distinct primes). Note that
each
a
i
is divisible by some term of this sequence.
1.6. Chinese Remainder Theorem
237
Since
p
k
1
1
,
p
k
2
2
, . . . ,
p
k
m
m
are pairwise relatively prime, the Chinese remainder
theorem yields a solution of the simultaneous congruences
x
≡
x
1
(
mod
p
k
1
1
),
x
≡
x
2
(
mod
p
k
2
2
), . . . ,
x
≡
x
m
(
mod
p
k
m
m
).
Now, since
P
(
x
)
is a polynomial with integer coefficients, the congruence
x
≡
x
j
(
mod
p
k
j
j
)
implies
P
(
x
)
≡
P
(
x
j
) (
mod
p
k
j
j
)
for each index
j
=
1
,
2
, . . . ,
m
.
By the definition of
p
k
j
j
, the number
P
(
x
j
)
is never divisible by
p
k
j
j
,
j
=
1
,
2
, . . .
,
m
. Thus, for the solution
x
given by the Chinese remainder theorem,
P
(
x
)
is not
divisible by any of the powers
p
k
j
j
. And because each
a
i
is divisible by some
p
k
j
j
,
j
=
1
,
2
, . . . ,
m
, it follows that no
a
i
divides
P
(
x
)
either, a contradiction.
Problem 1.6.4.
For any set
{
a
1
,
a
2
, . . . ,
a
n
}
of positive integers there exists a
positive integer b such that the set
{
ba
1
,
ba
2
, . . . ,
ba
n
}
consists of perfect powers.
Solution.
There is a finite number of primes
p
1
,
p
2
, . . . ,
p
k
that participate in the
prime factorization of
a
1
,
a
2
, . . . ,
a
n
. Let
a
i
=
p
α
i
1
1
p
α
i
2
2
· · ·
p
α
i k
k
for
i
=
1
,
2
, . . . ,
n
;
some of the exponents
α
i j
may be zeros. A positive integer with prime factoriza-
tion
p
u
1
1
p
u
2
2
· · ·
p
u
k
k
is a perfect
q
th power if and only if all the exponents
u
j
are
divisible by
q
. Thus it suffices to find positive integers
q
1
,
q
2
, . . . ,
q
n
greater than
1 and nonnegative integers
l
1
,
l
2
, . . . ,
l
k
such that
l
1
+
α
11
,
l
2
+
α
12
, . . . ,
l
k
+
α
1
k
are divisible by
q
1
,
l
1
+
α
21
,
l
2
+
α
22
, . . . ,
l
k
+
α
2
k
are divisible by
q
2
,
. . .
l
1
+
α
n
1
,
l
2
+
α
n
2
, . . . ,
l
k
+
α
nk
are divisible by
q
n
.
Now it is clear that we have many choices; let, for example,
q
i
be the
i
th prime
number. As far as
l
1
is concerned, the above conditions translate into
l
1
≡ −
α
j
1
(
mod
q
j
),
j
=
1
,
2
, . . . ,
n
.
This system of simultaneous congruences has a solution by the Chinese re-
mainder theorem, because
q
1
,
q
2
, . . . ,
q
n
are pairwise relatively prime. Analo-
gously, each of the systems of congruences
l
2
≡ −
α
j
2
(
mod
q
j
),
j
=
1
,
2
, . . . ,
n
,
l
3
≡ −
α
j
3
(
mod
q
j
),
j
=
1
,
2
, . . . ,
n
,
. . .
l
k
≡ −
α
j k
(
mod
q
j
),
j
=
1
,
2
, . . . ,
n
,
238
II Solutions, 1. Divisibility
is solvable for the same reason. Take
l
1
,
l
2
, . . . ,
l
k
such that all these congruences
are satisfied. Multiplying each
a
i
by
b
=
p
l
1
1
p
l
2
2
· · ·
p
l
k
k
yields a set
{
ba
1
,
ba
2
, . . .
,
ba
n
}
consisting of perfect powers (more exactly,
ba
i
is a perfect
q
i
th power).
Remarks.
(1) The following problem is a direct consequence of the above result:
Prove that for every positive integer n there exists a set of n positive integers
such that the sum of the elements of each of its subsets is a perfect power.
(Korean proposal for the 33rd International Mathematical Olympiad)
Indeed, let
{
x
1
,
x
2
, . . . ,
x
m
}
be a finite set of positive integers and
S
1
,
S
2
, . . .
,
S
r
the element sums of its nonempty subsets (
r
=
2
m
−
1). Choose a
b
such that
bS
1
,
bS
2
, . . . ,
bS
r
are all perfect powers. Then the set
{
bx
1
,
bx
2
, . . . ,
bx
m
}
yields
the desired example.
(2) Another consequence is the following:
There are arithmetic progressions
of arbitrary finite length consisting only of powers
. Yet, no such infinite progres-
sion exists.
1.7
Numerical Systems
Problem 1.7.12.
The natural number A has the following property: the sum of the
integers from
1
to A, inclusive, has decimal expansion equal to that of A followed
by three digits. Find A.
(1999 Russian Mathematical Olympiad)
Solution.
We know that
k
=
(
1
+
2
+ · · · +
A
)
−
1000
A
=
A
(
A
+
1
)
2
−
1000
A
=
A
A
+
1
2
−
1000
is between 0 and 999, inclusive. If
A
<
1999 then
k
is negative. If
A
≥
2000,
then
A
+
1
2
−
1000
≥
1
2
and
k
≥
1000. Therefore
A
=
1999, and indeed 1
+
2
+
· · · +
1999
=
1999000.
Problem 1.7.13.
A positive integer is said to be balanced if the number of its
decimal digits equals the number of its distinct prime factors. For instance,
15
is balanced, while
49
is not. Prove that there are only finitely many balanced
numbers.
(1999 Italian Mathematical Olympiad)
Solution.
Let
p
1
=
2,
p
2
=
3
, . . .
be the sequence of primes. If
x
is balanced and
it has
n
prime factors, then
10
n
≥
p
1
p
2
· · ·
p
n
≥
2
·
3
·
5
· · ·
(
2
n
−
1
) >
2
·
2
·
4
· · ·
(
2
n
−
2
) > (
n
−
1
)
!
,
which implies that
n
is bounded and so is
x
, since
x
≤
10
n
.
Do'stlaringiz bilan baham: |
