Mathématiques et algorithmique

Algorithme 12.2.1. Algorithme d'Euclide étendu.

• Entrées :

  • Assigner à \(\text{a}\) et \(\text{b}\) les deux entiers positifs dont on veut calculer le PGCD et un couple de coefficients de Bézout.

  • S'assurer qu'on a \(\text{a}\geq\text{b}\) si on ne veut pas faire une itération inutile.

• Instructions :

  • Assigner simultanément à \(\text{r0}\text{,}\) \(\text{u0}\text{,}\) \(\text{v0}\text{,}\) \(\text{r1}\text{,}\) \(\text{u1}\text{,}\) \(\text{v1}\) les valeurs \(\text{a}\text{,}\) \(\text{1}\text{,}\) \(\text{0}\text{,}\) \(\text{b}\text{,}\) \(\text{0}\text{,}\) \(\text{1}\text{.}\)

  • Tant que \(\text{r0}\,\%\,\text{r1}\neq 0\text{,}\)

    • assigner à \(\text{q}\) le quotient \(\text{r0}\,//\,\text{r1}\) ;

    • assigner simultanément à \(\text{r0}\text{,}\) \(\text{u0}\text{,}\) \(\text{v0}\text{,}\) \(\text{r1}\text{,}\) \(\text{u1}\text{,}\) \(\text{v1}\) les valeurs \(\text{r1}\text{,}\) \(\text{u1}\text{,}\) \(\text{v1}\text{,}\) \(\text{r0}\,\%\,\text{r1}\text{,}\) \(\text{u0}-\text{q}\cdot\text{u1}\text{,}\) \(\text{v0}-\text{q}\cdot\text{v1}\text{.}\)

• Sortie : Afficher \(\text{r1}\text{,}\) \(\text{u1}\text{,}\) \(\text{v1}\text{.}\)