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$

L'objectif

Trouver des entiers $u, v$ tels que $au + bv = \mathrm{pgcd}(a, b)$ .

Le principe

Le théorème de Bézout assure l'existence de $u, v \in \mathbb{Z}$ ; on les obtient en substituant chaque reste de l'algorithme d'Euclide sous forme de combinaison linéaire de $a$ et $b$ .

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.

Exemple corrigé

Difficulté croissante de 1 à 4

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

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

Exemple corrigé

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$