Number Theory: Structures, Examples, and Problems

II Solutions, 1. Divisibility
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)