Starting with an ordered quadruple of positive integers, a generalized Euclidean algorithm is applied successively as follows... Starting with an ordered quadruple of positive integers, a generalized Euclidean algorithm is applied successively as follows: if the numbers are $x, y, u, v$ and $x > y,$  then
the quadruple is replaced by $x − y, y, u + v, v.$ Otherwise, it is replaced by $x, y − x,
u, v + u.$
The algorithm stops when the numbers in the first pair become equal (in
which case they are equal to the greatest common divisor of x and y). Assume that we
start with $m, n, m, n.$ Prove that when the algorithm ends, the arithmetic mean of the
numbers in the second pair equals the least common multiple of $m$ and $n.$
The quantity $I = xv+yu$ does not change under the operation, so it remains equal to $2mn$
throughout the algorithm. When the first two numbers are both equal to $\gcd(m, n),$ the sum
of the latter two is $ \frac{2mn}{\gcd(m,n)}  = 2\operatorname{lcm}(m, n)$.
(St. Petersburg City Mathematical Olympiad, 1996)
Can you please explain why the sum of the latter two is $ \frac{2mn}{\gcd(m,n)}  = 2\operatorname{lcm}(m, n)$.
Also, a link to similar problems is also welcome.
 A: It helps to understand the idea behind the algorithm. It uses the subtractive Euclidean algorithm to change basis, iteratively transforming $\,m\Bbb Z + n\Bbb Z\,$ into $\,d\Bbb Z + d\Bbb Z = d\Bbb Z,\,$ where $\,d = \gcd(m,n),\,$ while simultaneously keeping track of the coordinates of some given number $\,k = v_0 m + u_0 n\,$ in each transformed basis. The (loop) invariant is that the bases are equivalent (same span), i.e. $\,x_j \Bbb Z + y_j\Bbb Z = m\Bbb Z + n\Bbb Z$. and that $\,v_j x_j + u_j y_j = k = v_0 x_0 + u_0 y_0,\,$ i.e. $\,(v_j,u_j)\,$ are the coordinates of $\,k\,$ in the current basis $\,(x_j,y_j).\,$  Span persistence follows because the subtractive Euclidean algorithm changes bases via elementary transformations (i.e. determinant $=\pm1),\,$ which are invertible. The coordinate persistence follows by simple algebra, naturally viewed as persistence of the determinant under column operations, i.e. if we represent $(x,y,u,v)$ by $\begin{bmatrix}  x & y\\ -u & v \end{bmatrix}$ then the Euclidean reduction step subtracts the column with least first row entry from the other column, which preserves the determinant, e.g. if $\,x < y\,$ then the reduction step simply subtracts the $\rm\color{#c00}{second}$ column from the first, as displayed below
$$\begin{align} (x,y,u,v)\  &\to\  (x\!-\!y,y, u\!+\!v,v)\,\ \ \text{has matrix form below:}\\[.5em]
 \begin{bmatrix}  \ \ x & \color{#c00}y\\ -u & \color{#c00}v \end{bmatrix} 
\ &\to \ \begin{bmatrix}  \,\ \ x-\color{#c00}y  & y\\ -(u+\color{#c00}v) & v \end{bmatrix}
 =  \begin{bmatrix}  \ \ x & y\\ -u & v \end{bmatrix} 
 \begin{bmatrix}  \ \ 1 & 0\\ -1 & 1 \end{bmatrix} \end{align}\qquad$$
Since the reduction step amounts to multiplying by a matrix with determinant $=1$ it preserves the determinant (our loop  invariant $I)$. Thus the algorithm may be viewed as column subtractions on these matrices, which amounts to augmenting the subtractive Euclidean algorithm (on rows $[x,y])$ to $\,2\times 2\,$ matrices, by appending a 2nd row $[-u,v]$ for the coordinates of the given number.
Finally, to answer your question about the invariant at termination. note that in the OP we have   $\,v_0,u_0 = n,m\,$ so $\, k = 2mn,\,$ so when the algorithm terminates with $\,x = y = d\,$ we have
$$\begin{align} \overbrace{\color{#c00}d(v\!+\!u)}^{\textstyle \color{#c00}xv+\color{#c00}yu} &=\, 2mn\\[.4em]  \iff \frac{v+u}2 &= \frac{mn}d = {\rm lcm}(m,n)\end{align}\qquad$$
where we used $\,d\,{\rm lcm}(m,n) = \gcd(m,n)\,{\rm lcm}(m,n) = mn\,$ by here.
Remark $ $ To learn more about the linear algebra at the heart of the matter see the Hermite - Smith normal form and closely related topics.
A: It is a theorem that $\operatorname{LCM}(m,n)\operatorname{GCD}(m,n)=mn$.  To see this, consider the powers of a prime dividing $m,n$  The maximum is a factor of the $\operatorname{GCD}$, the minimum is a factor of the $\operatorname{LCM}$ so the powers on each side are equal.
To see the invariance, apply the rule.  We assume $x \gt y$ and use primes for the new variable values
$$x'v'+y'u'=(x-y)v+y(u+v)=xv+yu$$
The other case is similar
