Algorithme d'Euclide étendu (sans tableau)

Les propriétés utilisées dans les tableaux sont basées sur le raisonnement suivant :

• Si $b = 0$, alors $pgcd(a, b) = a$, et on a $1.a + 0.b = pgcd(a, b)$
• Par récurrence, appliquons la même méthode au couple $(b, a \ mod\ b)$, alors on a $u$ et $v$ tels que
  
  $$u.b + v.(a \ mod\ b) = pgcd(b, a \ mod\ b)$$
  
  
  Soit $\lfloor\frac{a}{b}\rfloor$ le quotient de la division de $a$ par $b$, alors
  
  $$a \ mod\ b = a - \lfloor\frac{a}{b}\rfloor b$$
  
  
  Donc
  
  $$u.b + v.(a - \lfloor\frac{a}{b}\rfloor b) = pgcd(b, a \ mod\ b)$$
  
  
  Ce qui se réécrit
  
  $$v.a + (u - v \lfloor\frac{a}{b}\rfloor)b = pgcd(b, a \ mod\ b)$$
  
  
  Comme, de plus,
  
  $$pgcd(a, b) = pgcd(b, a \ mod\ b)$$
  
  
  alors
  
  $$v.a + (u - v \lfloor\frac{a}{b}\rfloor)b = pgcd(a, b)$$
  
  
  Donc, en posant $u^\prime = v$ et $v^\prime = u - v \lfloor\frac{a}{b}\rfloor$, on a bien
  
  $$u^\prime.a + v^\prime.b = pgcd(a, b)$$