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$

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

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.

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

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

Étape 1 —

Effectuer l'algorithme d'Euclide et noter toutes les divisions successives :

r_{k-2} = r_{k-1} q_k + r_k

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

Étape 2 —

Isoler le dernier reste non nul (= PGCD) et exprimer chaque reste précédent comme combinaison linéaire de

a

b

, en remontant les étapes de bas en haut.

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

Étape 3 —

Effectuer les substitutions successives pour obtenir finalement

\mathrm{pgcd}(a,b) = au + bv

et vérifier.

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

Application guidée

Coefficients de Bézout pour $\mathrm{pgcd}(252, 105) = 21$

Application autonome 1

Coefficients de Bézout pour $\mathrm{pgcd}(35, 12) = 1$

Application autonome 2

Coefficients de Bézout pour $\mathrm{pgcd}(1071, 462) = 21$

Application autonome 3

Coefficients de Bézout pour $\mathrm{pgcd}(56, 15) = 1$ .

Crée ton compte gratuit pour accéder à la fiche et aux exercices

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, fais des exercices !

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$