# 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).$

• Factoring with the Factor Tree
• GCD and LCM via Factor Tree
• GCD and LCM by Plain Factorization
• Common Multiples and the Least Common Multiple
• GCD(M, N) x LCM(M, N) = M x N
• Divisibility Criteria
• Euclid's Algorithm
• Algorithm for Computing the LCM
• Factors And Multiples
• Two Properties of Greatest Common Divisor
• Properties of GCD and LCM
• A Line in a Square Grid
• Number of Factors of an Integer

• A Three Pegs Question
• Solitaire on a Circle
• Peg Solitaire
• The Game of Fif
• Nim
• Sums and Products
• Splitting Piles
• Chameleons of Three Colors
• Moving Chips in Pairs Down a Checkerboard
• White and Black Balls in Urn. 1 in, 2 out. What Color Remains?