|
Solution.
Note that
x
v
+
yu
does not change under the operation, so it remains
equal to 2
mn
throughout. Thus when the first two numbers both equal gcd
(
m
,
n
)
,
the sum of the latter two is 2
mn
/
gcd
(
m
,
n
)
=
2 lcm
(
m
,
n
)
.
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)
Solution.
First, note that there are 15 primes from 1 to 50:
(
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
,
31
,
37
,
41
,
43
,
47
).
To make this easier, let us define
f
(
a
,
b
)
to be greatest power of
b
dividing
a
.
(Note that
g
(
50
!
,
b
) >
g
(
5
!
,
b
)
for all
b
<
50.) Therefore, for each prime
p
, we
have either
f
(
x
,
p
)
=
f
(
5
!
,
p
)
and
f
(
y
,
p
)
=
f
(
50
!
,
p
)
or
f
(
y
,
p
)
=
f
(
5
!
,
p
)
and
f
(
x
,
p
)
=
f
(
50
!
,
p
)
. Since we have 15 primes, this gives 2
15
pairs, and
clearly
x
=
y
in any such pair (since the greatest common divisor and least
common multiple are different), so there are 2
14
pairs with
x
≤
y
.
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)
Solution.
If
a
,
b
are erased and
c
<
d
are written instead, we have
c
≤
min
(
a
,
b
)
and
d
≥
max
(
a
,
b
)
; moreover,
ab
=
cd
. From this we may conclude that
a
+
b
≤
c
+
d
. Indeed,
ab
+
a
2
=
cd
+
a
2
≤
ac
+
ad
(the latter since
(
d
−
a
)(
c
−
a
)
≤
0)
and divide both sides by
a
. Thus the sum of the numbers never decreases, and it
is obviously bounded (e.g., by
n
times the product of the numbers, where
n
is the
number of numbers on the board); hence it eventually stops changing, at which
time the numbers never change.
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)
1.3. The Greatest Common Divisor and Least Common Multiple
229
Solution.
(a) Let
x
=
1998
a
,
y
=
1998
b
. So
a
,
b
are positive integers such that
a
<
b
, gcd
(
a
,
b
)
=
1. We have lcm
(
x
,
y
)
=
1998
ab
=
2
·
3
3
·
37
ab
=
n
!
. Thus
n
≥
37 and it is easy to see that this condition is also sufficient.
(b) The answers are
n
=
37
,
38
,
39
,
40. We need to consider only positive
integers
n
≥
37. For 37
≤
n
<
41, let
k
=
ab
=
n
!
/
1998. Since gcd
(
a
,
b
)
=
1,
any prime factor of
k
that occurs in
a
cannot occur in
b
, and vice versa. There are
11 prime factors of
k
, namely 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. For each of
those prime factors, one must decide only whether it occurs in
a
or in
b
. These
11 decisions can be made in a total of 2
11
=
2048 ways. However, only half of
these ways will satisfy the condition
a
<
b
. Thus there will be a total of 1024
such pairs of
(
x
,
y
)
for
n
=
37, 38, 39, 40. Since 41 is a prime, we can see by a
similar argument that there will be at least 2048 such pairs of
(
x
,
y
)
for
n
≥
41.
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)
Solution.
Such an
f
exists for
k
=
0 and
k
= −
1. First take
a
=
b
in (b) to get
f
(
a
2
)
=
(
k
+
2
)
f
(
a
)
. Applying this twice, we get
f
(
a
4
)
=
(
k
+
2
)
f
(
a
2
)
=
(
k
+
2
)
2
f
(
a
).
On the other hand,
f
(
a
4
)
=
f
(
a
)
+
f
(
a
3
)
+
k f
(
a
)
=
(
k
+
1
)
f
(
a
)
+
f
(
a
3
)
=
(
k
+
1
)
f
(
a
)
+
f
(
a
)
+
f
(
a
2
)
+
k f
(
a
)
=
(
2
k
+
2
)
f
(
a
)
+
f
(
a
2
)
=
(
3
k
+
4
)
f
(
a
).
Setting
a
=
1997, so that
f
(
a
)
=
0, we deduce that
(
k
+
2
)
2
=
3
k
+
4, which
has roots
k
=
0
,
−
1. For
k
=
0, an example is given by
f
(
p
e
1
1
· · ·
p
e
n
n
)
=
e
1
g
(
p
1
)
+ · · · +
e
n
g
(
p
n
),
g
(
1
,
97
)
=
1998, and
g
(
p
)
=
0 for all primes
p
=
1997. For
k
= −
1, an example
is given by
f
(
p
e
1
1
· · ·
p
e
n
n
)
=
g
(
p
1
)
+ · · · +
g
(
p
n
).
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)
230
II Solutions, 1. Divisibility
Solution.
All solutions are of the form
(
a
2
−
1
,
a
,
1
)
with
a
even. We have
x
n
=
y
n
+
1
−
1
=
(
y
−
1
)
m
with
m
=
y
n
+
y
n
−
1
+ · · · +
y
+
1. Thus
m
|
x
n
and
gcd
(
m
,
n
+
1
)
=
1. Rewrite
m
as
m
=
(
y
−
1
)(
y
n
−
1
+
2
y
n
−
2
+
3
y
n
−
3
+ · · · +
(
n
−
1
)
y
+
n
)
+
(
n
+
1
).
Thus we have gcd
(
m
,
y
−
1
)
|
n
+
1. But gcd
(
m
,
n
+
1
)
=
1, so gcd
(
m
,
y
−
1
)
=
1.
Since
x
n
=
(
y
−
1
)
m
,
m
must be a perfect
n
th power. But
(
y
+
1
)
n
=
y
n
+
n
1
y
n
−
1
+ · · · +
n
n
−
1
y
+
1
>
m
>
y
n
,
for
n
>
1. So
m
can be a perfect
n
th power only if
n
=
1 and
x
=
y
2
−
1. Since
x
and
n
+
1
=
2 are relatively prime,
y
must be even, yielding the presented
solutions.
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)
Solution.
The only solution is
l
=
m
=
n
=
2. Let
d
=
gcd
(
l
,
m
,
n
)
, and put
l
=
dl
1
,
m
=
dm
1
,
n
=
dn
1
. Then
d
(
m
1
+
n
1
)
=
d
2
d
2
mn
, where
d
mn
=
gcd
(
m
1
,
n
1
)
,
so
m
1
+
n
1
=
dd
2
mn
. Defining
d
ln
and
d
lm
likewise, we get
2
(
l
1
+
m
1
+
n
1
)
=
d
(
d
2
lm
+
d
2
ln
+
d
2
mn
).
Since
d
/
gcd
(
d
,
2
)
divides
l
1
+
m
1
+
n
1
as well as
m
1
+
n
1
, it divides
l
1
and likewise
m
1
and
n
1
. Since these three numbers are relatively prime, we have
d
/
gcd
(
d
,
2
)
=
1, and so
d
≤
2.
Note that
d
lm
,
d
ln
,
d
mn
are pairwise relatively prime; therefore we can write
l
1
=
l
2
d
lm
d
ln
,
m
1
=
m
2
d
lm
d
mn
,
n
1
=
n
2
d
ln
d
mn
. Then we have
d
lm
d
mn
m
2
+
d
ln
d
mn
n
2
=
dd
2
mn
,
and so
m
2
d
lm
+
n
2
d
ln
=
dd
mn
, and so forth. Assuming without loss of generality
that
d
mn
is no larger than
d
lm
,
d
ln
, we get
2
d
mn
≥
dd
mn
=
d
lm
m
2
+
d
ln
n
2
≥
d
lm
+
d
ln
≥
2
d
mn
.
Thus we have equality throughout:
d
=
2,
m
2
=
n
2
=
1, and
d
lm
=
d
ln
=
d
mn
. But these three numbers are pairwise relatively prime, so they are all 1. Then
m
1
=
n
1
=
1 and from
l
1
+
m
1
=
dd
2
lm
,
l
1
=
1 as well. Therefore
l
=
m
=
n
=
2.
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: |
