|
I Fundamentals, 1. Divisibility
It suffices to show that for each nonnegative numbers
α
,
β
, and
γ
min
{
α, β
} +
min
{
β, γ
} +
min
{
γ, α
} −
2 min
{
α, β, γ
}
=
max
{
α, β
} +
max
{
β, γ
} +
max
{
γ, α
} −
2 max
{
α, β, γ
}
.
By symmetry, we may assume that
α
≤
β
≤
γ
. It is not difficult to deduce
that both sides are equal to
β
, completing our proof.
Problem 1.3.7.
Let m
≥
2
be an integer. A positive integer n is called m-good if
for every positive integer a relatively prime to n, one has n
|
a
m
−
1
.
Show that every m-good number is at most
4
m
(
2
m
−
1
)
.
(2004 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
If
m
is odd, then
n
|
(
n
−
1
)
m
−
1 implies
n
|
2; hence
n
≤
2.
Take now
m
=
2
t
q
,
t
≥
1,
q
odd. If
n
=
2
u
(
2
v
+
1
)
is
m
-good, then
(
2
v
+
1
)
|
(
2
v
−
1
)
m
−
1; hence
(
2
v
+
1
)
|
2
m
−
1. Also, if
a
=
8
v
+
5, then gcd
(
a
,
n
)
=
1,
so
2
u
|
(
a
q
)
2
t
−
1
=
(
a
q
−
1
)(
a
q
+
1
)(
a
2
q
+
1
)
· · ·
(
a
2
t
−
1
q
+
1
).
Since
q
is odd,
a
q
=
8
V
+
5 for some integer
V
. Hence the first term in the
product is divisible by 2
2
, but not 2
3
. Similarly, the other terms are divisible by
2, but not 2
2
. Hence the product is divisible by 2
t
+
1
and no higher power of 2.
Therefore
u
≤
t
+
2, whence
n
≤
4
·
2
t
(
2
v
+
1
)
≤
4
m
(
2
m
−
1
)
.
The estimate is optimal only for
m
=
2,
m
=
4.
Problem 1.3.8.
Find all triples of positive integers
(
a
,
b
,
c
)
such that a
3
+
b
3
+
c
3
is divisible by a
2
b, b
2
c, and c
2
a.
(2001 Bulgarian Mathematical Olympiad)
Solution.
Answer: triples of the form
(
k
,
k
,
k
)
or
(
k
,
2
k
,
3
k
)
or their permutations.
Let
g
be the positive greatest common divisor of
a
and
b
. Then
g
3
divides
a
2
b
, so
g
3
divides
a
3
+
b
3
+
c
3
, and
g
divides
c
. Thus, the gcd of any two of
a
,
b
,
c
is the gcd of all three.
Let
(
l
,
m
,
n
)
=
(
a
/
g
,
b
/
g
,
c
/
g
)
. Then
(
l
,
m
,
n
)
is a triple satisfying the con-
ditions of the problem, and
l
,
m
,
n
are pairwise relatively prime. Because
l
2
,
m
2
,
and
n
2
all divide
l
3
+
m
3
+
n
3
, we have
l
2
m
2
n
2
|
(
l
3
+
m
3
+
n
3
).
We will prove that
(
l
,
m
,
n
)
is either
(
1
,
1
,
1
)
or a permutation of
(
1
,
2
,
3
)
.
Assume without loss of generality that
l
≥
m
≥
n
. We have
3
l
3
≥
l
3
+
m
3
+
n
3
≥
l
2
m
2
n
2
,
1.3. The Greatest Common Divisor and Least Common Multiple
25
and therefore
l
≥
m
2
n
2
/
3. Because
l
2
|
(
m
3
+
n
3
)
, we also have
2
m
3
≥
m
3
+
n
3
≥
l
2
≥
m
4
n
4
/
9
.
If
n
≥
2, then
m
≤
2
·
9
/
2
4
<
2
≤
n
, which contradicts the assumption that
m
≥
n
. Therefore,
n
must be 1. If
m
=
n
=
1, then
l
2
|
m
3
+
n
3
=
2 so
l
=
1 and
we get the unique solution
(
1
,
1
,
1
)
.
If
m
≥
2, then
l
>
m
, because
l
and
m
are relatively prime, so
2
l
3
>
l
3
+
m
3
+
1
≥
l
2
m
2
,
and
l
>
m
2
/
2, so
m
3
+
1
≥
l
2
>
m
4
/
4
,
and
m
≤
4. If
m
=
2, then
l
2
|
m
3
+
1
=
9 and
l
≥
m
; hence
l
=
3 and we get the
solution
(
3
,
2
,
1
)
. If
m
=
3 or 4, then
l
2
|
m
3
+
1 and
l
≥
m
gives a contradiction.
Additional Problems
Problem 1.3.9.
A sequence
a
1
,
a
2
, . . .
of natural numbers satisfies
gcd
(
a
i
,
a
j
)
=
gcd
(
i
,
j
)
for all
i
=
j
.
Prove that
a
i
=
i
for all
i
.
(1995 Russian Mathematical Olympiad)
Problem 1.3.10.
The natural numbers
a
and
b
are such that
a
+
1
b
+
b
+
1
a
is an integer. Show that the greatest common divisor of
a
and
b
is not greater than
√
a
+
b
.
(1996 Spanish Mathematical Olympiad)
Problem 1.3.11.
The positive integers
m
,
n
,
m
,
n
are written on a blackboard. A
generalized Euclidean algorithm is applied to this quadruple as follows: if the
numbers
x
,
y
,
u
, v
appear on the board and
x
>
y
, then
x
−
y
,
y
,
u
+
v
,
v
are
written instead; otherwise
x
,
y
−
x
,
u
,
v
+
u
are written instead. The algorithm
stops when the numbers in the first pair become equal (they will equal the greatest
common divisor of
m
and
n
). Prove that the arithmetic mean of the numbers in
the second pair at that moment equals the least common multiple of
m
and
n
.
(1996 St. Petersburg City Mathematical Olympiad)
26
I Fundamentals, 1. Divisibility
Problem 1.3.12.
How many pairs
(
x
,
y
)
of positive integers with
x
≤
y
satisfy
gcd
(
x
,
y
)
=
5
!
and lcm
(
x
,
y
)
=
50
!
?
(1997 Canadian Mathematical Olympiad)
Problem 1.3.13.
Several positive integers are written on a blackboard. One can
erase any two distinct integers and write their greatest common divisor and least
common multiple instead. Prove that eventually the numbers will stop changing.
(1996 St. Petersburg City Mathematical Olympiad)
Problem 1.3.14.
(a) For which positive integers
n
do there exist positive integers
x
,
y
such that
lcm
(
x
,
y
)
=
n
!
,
gcd
(
x
,
y
)
=
1998?
(b) For which
n
is the number of such pairs
x
,
y
with
x
≤
y
less than 1998?
(1998 Hungarian Mathematical Olympiad)
Problem 1.3.15.
Determine all integers
k
for which there exists a function
f
:
N
→
Z
such that
(a)
f
(
1997
)
=
1998;
(b) for all
a
,
b
∈
N
,
f
(
ab
)
=
f
(
a
)
+
f
(
b
)
+
k f
(
gcd
(
a
,
b
))
.
(1997 Taiwanese Mathematical Olympiad)
Problem 1.3.16.
Find all triples
(
x
,
y
,
n
)
of positive integers such that
gcd
(
x
,
n
+
1
)
=
1 and
x
n
+
1
=
y
n
+
1
.
(1998 Indian Mathematical Olympiad)
Problem 1.3.17.
Find all triples
(
m
,
n
,
l
)
of positive integers such that
m
+
n
=
gcd
(
m
,
n
)
2
,
m
+
l
=
gcd
(
m
,
l
)
2
,
n
+
l
=
gcd
(
n
,
l
)
2
.
(1997 Russian Mathematical Olympiad)
Problem 1.3.18.
Let
a
,
b
be positive integers such that gcd
(
a
,
b
)
=
1. Find all
pairs
(
m
,
n
)
of positive integers such that
a
m
+
b
m
divides
a
n
+
b
n
.
(Mathematical Reflections)
Do'stlaringiz bilan baham: |
