MathDB
Problems
Contests
National and Regional Contests
Indonesia Contests
Indonesia MO
2021 Indonesia MO
6
6
Part of
2021 Indonesia MO
Problems
(1)
Produce same numbers on the board!
Source: Indonesia National Math Olympiad 2021 Problem 6 (INAMO 2021/6)
11/9/2021
There are
n
n
n
natural numbers written on the board. Every move, we could erase
a
,
b
a,b
a
,
b
and change it to
gcd
(
a
,
b
)
\gcd(a,b)
g
cd
(
a
,
b
)
and
lcm
(
a
,
b
)
−
gcd
(
a
,
b
)
\text{lcm}(a,b) - \gcd(a,b)
lcm
(
a
,
b
)
−
g
cd
(
a
,
b
)
. Prove that in finite number of moves, all numbers in the board could be made to be equal.
number theory
algorithm