Calcul du PGCD et PPCM par un jeu d'invariants

On considère un jeu pour calculer le pgcd de deux entiers $a$ et $b$ et leur ppcm. On part de :

$$x=a,y=b,u=a,v=b$$

et on joue comme suit :

• si $x<y$, on remplace $y$ par $y-x$, et $v$ par $v+u$ ;
• si $x>y$, on remplace $x$ par $x-y$, et $u$ par $u+v$.

Montrer que le jeu termine avec :

$$x=y=\gcd (a,b)\text{et}\frac{u+v}{2}=\text{lcm}(a,b).$$