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.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

 

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


Related material
Read more...

  • 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

    • Related material
    Read more...

  • 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?

    • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    72190271