# Extension of Euclid's Game

Consider the following game:

Start with two positive integers $a$ and $b,$ set $x=u=a$ and $y=v=b,$ and proceed to execute the following steps one at a time:

$\begin{cases} x\leftarrow x-y,\,u\leftarrow u+v, & \mbox{if }x\gt y,\\ y\leftarrow y-x,\,v\leftarrow u+v, & \mbox{if }x\lt y,\\ \mbox{STOP} & \mbox{if } x=y. \end{cases}$

Prove that eventually the process does stop. When it stops, $x=y=\mbox{GCD} (a,b)$ and $\displaystyle\frac{u+v}{2}=\mbox{LCM} (a,b).$

(The left arrow, as in $X\leftarrow Y,$ means the assignment to $X$ of the value of $Y.)$ As usual, $\mbox{GCD} (a,b)$ is the Greatest Common Divisor, $\mbox{LCM} (a,b)$ the Least Common Multiple of $a$ and $b$.

Solution

### References

1. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, 1.20.

Start with two positive integers $a$ and $b,$ set $x=u=a$ and $y=v=b,$ and proceed to execute the following steps one at a time:

$\begin{cases} x\leftarrow x-y,\,u\leftarrow u+v, & \mbox{if }x\gt y,\\ y\leftarrow y-x,\,v\leftarrow u+v, & \mbox{if }x\lt y,\\ \mbox{STOP} & \mbox{if } x=y. \end{cases}$

Prove that eventually the process does stop. When it stops, $x=y=\mbox{GCD} (a,b)$ and $\displaystyle\frac{u+v}{2}=\mbox{LCM} (a,b).$

### Solution

The two claims (that the process stops and, when it does, $x=y=\mbox{GCD} (a,b))$ is just a reformulation of Euclid's game. Let's focus on proving that at the end $\displaystyle\frac{u+v}{2}=\mbox{LCM} (a,b).$

Observe that the expression $P=xv+yu$ remains invariant at every step of the process. Indeed, if $x\gt y,$ then $(x-y)v+y(u+v)=xu+yv.$ If $x\lt y,$ then $x(u+v)+(y-x)v=xu+yv.$ Note also that the beginning $P=2ab.$ Now, when $x=y$ we get

$\displaystyle 2ab=xv+yu=x(u+v)=\mbox{GCD}(a,b)\cdot 2\frac{u+v}{2},$

such that $\displaystyle \frac{u+v}{2}=\frac{ab}{\mbox{GCD} (a,b)}$ which exactly means that $\displaystyle\frac{u+v}{2}=\mbox{LCM} (a,b).$

[an error occurred while processing this directive]

[an error occurred while processing this directive]