Comment exprimer le PGCD sous la forme de Bézout $au + bv$ ?

En remontant les étapes de l'algorithme d'Euclide (algorithme d'Euclide étendu) : exprimer chaque reste comme combinaison linéaire de $a$ et $b$ jusqu'à obtenir $\mathrm{pgcd}(a,b) = au + bv$

Que ferais-tu face à un exercice de ce type ?

Coefficients de Bézout pour $\mathrm{pgcd}(48, 18) = 6$

La méthode

1
Effectuer l'algorithme d'Euclide et noter toutes les divisions successives : $r_{k-2} = r_{k-1} q_k + r_k$ .
Comment calculer le PGCD de deux entiers ?Voir
2
Isoler le dernier reste non nul (= PGCD) et exprimer chaque reste précédent comme combinaison linéaire de $a$ et $b$ , en remontant les étapes de bas en haut.
3
Effectuer les substitutions successives pour obtenir finalement $\mathrm{pgcd}(a,b) = au + bv$ et vérifier.

Pour comprendre, passons aux exercices.

Exercice d'exemple

Coefficients de Bézout pour $\mathrm{pgcd}(48, 18) = 6$

1

Algorithme d'Euclide : $48 = 18 \times 2 + 12$ , puis $18 = 12 \times 1 + 6$ , puis $12 = 6 \times 2 + 0$ .

2

On isole $6 = 18 - 12 \times 1$ . On substitue $12 = 48 - 18 \times 2$ : $6 = 18 - (48 - 18 \times 2) = 18 \times 3 - 48$ .

3

$6 = 48 \times (-1) + 18 \times 3$ . Vérification : $-48 + 54 = 6$ . ✓

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment exprimer le PGCD sous la forme de Bézout au+bvau + bvau+bv ?

En remontant les étapes de l'algorithme d'Euclide (algorithme d'Euclide étendu) : exprimer chaque reste comme combinaison linéaire de aaa et bbb jusqu'à obtenir pgcd(a,b)=au+bv\mathrm{pgcd}(a,b) = au + bvpgcd(a,b)=au+bv

Pour comprendre, passons aux exercices.

Comment exprimer le PGCD sous la forme de Bézout $au + bv$ ?

En remontant les étapes de l'algorithme d'Euclide (algorithme d'Euclide étendu) : exprimer chaque reste comme combinaison linéaire de $a$ et $b$ jusqu'à obtenir $\mathrm{pgcd}(a,b) = au + bv$