L'algorithme d'Euclide étendu permet, outre le calcul le calcul du PGCD de deux entiers naturels non nuls $a$ et $b$, de déterminer les entiers relatifs $u$ et $v$ tels que $au+bv=PGCD\left(a;b\right)$.

On procède comme pour l'algorithme d'Euclide (voir algorithme d'Euclide) mais à chaque étape on cherche à écrire le reste $r$ comme combinaison linéaire de $a$ et de $b$.

Exemple

On veut monter que a=135 et b=101 sont premiers entre eux et on recherche les entiers relatifs $u$ et $v$ tels que $135u+101v=1$.

(le tableau ci-dessous peut être obtenu avec l'outil Outil : Coefficient de Bézout)

Ligne 1 : On effectue la division euclidienne de 135 par 101. Le quotient est 1 et le reste 34.

Cette division s'écrit : 135 = 1×101 + 34

On en déduit (colonne combinaison) que 34 = 135 - 1×101

Par conséquent, 34 s'écrit comme combinaison linéaire de a et de b :

Ligne 2 : Dans la colonne "Dividende", on place le diviseur de la ligne précédente soit 101.

Dans la colonne "Diviseur", on place le reste de la ligne précédente soit 34.

On effectue ensuite la division euclidienne de 101 par 34. Le quotient est 2 et le reste 33.

Cette division s'écrit : 101 = 2×34 + 33

c'est à dire 33 = 101 - 2×34

Or 101 = 0×a + 1×b (ou plus simplement 101 = b...)

et d'après la ligne 1 : 34 = 1×a - 1×b

par conséquent : 33 = (0×a + 1×b) - 2×(1×a - 1×b)

33 s'écrit donc comme combinaison linéaire de a et de b :

Ligne 3 : Dans la colonne "Dividende", on place le diviseur de la ligne précédente soit 34.

Dans la colonne "Diviseur", on place le reste de la ligne précédente soit 33.

On effectue alors la division euclidienne de 34 par 33. Le quotient est 1 et le reste est également 1.

Cette division s'écrit : 34 = 1×33 + 1

c'est à dire 1=34-1×33

Or d'après la ligne 1 : 34 = 1×a - 1×b

et d'après la ligne 2 : 33 = -2×a + 3×b

par conséquent : 1 = (1×a - 1×b) - 1×(-2×a + 3×b)

1 s'écrit donc comme combinaison linéaire de a et de b :

Ligne 4 : (facultative ici, car on trouve r=1 à l'étape précédente; on sait donc déjà que $a$ et $b$ sont premiers entre eux)

Dans la colonne "Dividende", on place le diviseur de la ligne précédente soit 33.

Dans la colonne "Diviseur", on place le reste de la ligne précédente soit 1.

On effectue la division euclidienne de 33 par 1 : le reste est nul donc on a donc terminé le calcul.

Le PGCD est le dernier entier non nul dans la colonne des restes. C'est donc 1.

Conclusion :135 et 101 sont premiers entre eux.

La ligne 3 donne l'égalité de Bézout :

c'est à dire :