Algorithme d'Euclide étendu : méthode (MPSI)

Méthode

Algorithme d'Euclide étendu

Pour obtenir $(u, v)$ tel que $au + bv = a \wedge b$ :

On mène l'algorithme d'Euclide en tenant à jour, pour chaque reste, une écriture $r_k = a u_k + b v_k$.
Initialisation : $(r_0, u_0, v_0) = (a, 1, 0)$ et $(r_1, u_1, v_1) = (b, 0, 1)$.
Si $q_k$ est le quotient de $r_{k-1}$ par $r_k$, on calcule la ligne suivante par la même opération sur les trois colonnes : $$r_{k+1} = r_{k-1} - q_k r_k, \quad u_{k+1} = u_{k-1} - q_k u_k, \quad v_{k+1} = v_{k-1} - q_k v_k.$$
La ligne du dernier reste non nul fournit $(u, v)$.

On peut aussi « remonter » les divisions à la main, en exprimant chaque reste à partir des précédents.

Exemple

Coefficients de Bézout pour $1071$ et $462$

$k$	$r_k$	$u_k$	$v_k$	$q_k$
0	1071	1	0
1	462	0	1	2
2	147	1	$-2$	3
3	21	$-3$	7	7
4	0

On obtient $1071 \times (-3) + 462 \times 7 = 21$. Vérification : $462 \times 7 = 3234$ et $1071 \times 3 = 3213$, différence $21$.

En remontant : $21 = 462 - 3 \times 147 = 462 - 3(1071 - 2 \times 462) = 7 \times 462 - 3 \times 1071$.

S’entraîner