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)
| Dividende | Diviseur | q | r | Combinaison | |
| 1 | 135 | 101 | 1 | 34 | 34 = 135 – 1×101 34 = 1×a – 1×b |
| 2 | 101 | 34 | 2 | 33 | 33 = 101 – 2×34 33 = (0×a + 1×b) – 2×(1×a – 1×b) 33 = -2×a + 3×b |
| 3 | 34 | 33 | 1 | 1 | 1 = 34 – 1×33 |
| 4 | 33 | 1 | 33 | 0 |
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 :
34 = 1×a – 1×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 :
33 = -2×a + 3×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 :
1 = 3×a – 4×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 :
3×a – 4×b = 1
c’est à dire :
3×135 – 4×101 = 1