Algorithme d'Euclide étendu (avec tableau)

Il possible d'enrichir l'algorithme d'Euclide afin qu'il calcule les coefficients $u$ et $b$ de la relation de Bezout. Étant donnés deux nombres $a$ et $b$, on représente dans un tableau les étapes de l'exécution de l'algorithme d'Euclide de la façon suivante (nous noterons $\lfloor\frac{a}{b}\rfloor$ le quotient de la division de $a$ par $b$):

$a$	$b$	$\lfloor\frac{a}{b}\rfloor$	$a\ mod\ b$
$8$	$5$	$1$	$3$
$5$	$3$	$1$	$2$
$3$	$2$	$1$	$1$
$2$	$1$	$2$	$0$
$1$	$0$

On remarque que l'on passe d'une ligne du tableau à la suivante de la façon suivante :

$a$	$b$	$\lfloor\frac{a}{b}\rfloor$	$a\ mod\ b$
$b$	$a\ mod\ b$

On s'arrête à la ligne qui conduit à une division par $0$ est le $pgcd$ se trouve dans $a$. On étend l'algorithme d'Euclide en ajoutant deux colonnes $u$ et $v$ que l'on renseigne de la façon suivante :

$a$	$b$	$\lfloor\frac{a}{b}\rfloor$	$a\ mod\ b$	$v$	$u - v\lfloor\frac{a}{b}\rfloor$
				$u$	$v$

On remplit donc les deux dernières colonnes en partant de la dernière ligne du tableau et en remontant jusqu'à la première. La dernière ligne s'initialise de la façon suivante :

$a$

$0$

$1$

$v$

où $v$ est un entier relatif arbitraire (dans l'exemple suivant la première valeur de $v$ est $2$). Dans l'exemple précédent cela donne :

$a$	$b$	$\lfloor\frac{a}{b}\rfloor$	$a\ mod\ b$	$u$	$v$
$8$	$5$	$1$	$3$	$-8$	$13$
$5$	$3$	$1$	$2$	$5$	$-8$
$3$	$2$	$1$	$1$	$-3$	$5$
$2$	$1$	$2$	$0$	$2$	$-3$
$1$	$0$			$1$	$2$