Identité de Bézout

Énoncé

Trouver des entiers u et v tels que 84u + 60v = PGCD(84, 60).

Indice : Remonte les divisions euclidiennes de l'algorithme d'Euclide pour exprimer le PGCD en fonction de 84 et 60.

Correction

1. Étape 1 : On sait qu'un couple (u,v) existe (théorème de Bézout), il s'agit de le TROUVER. La méthode consiste à remonter l'algorithme d'Euclide du 37005, en remplaçant chaque reste par son expression.
2. Étape 2 : On repart des divisions du 37005, en isolant chaque reste :

   24 = 84 - 60 1 12 = 60 - 24 2

3. Étape 3 : On substitue la première dans la seconde, pour faire disparaître le 24 — car seuls 84 et 60 doivent subsister à la fin :

   12 = 60 - 2\,(84 - 60)

4. Étape 4 : On développe et on regroupe en 84 et 60 :

   12 = 60 - 2 84 + 2 60 = -2 84 + 3 60

5. Étape 5 : D'où le couple cherché :

   u = -2 v = 3

6. Étape 6 : Vérification, indispensable après une substitution :

   84 (-2) + 60 3 = -168 + 180 = 12 \

7. Étape 7 : Le couple n'est pas unique. En ajoutant 5 à u et en retranchant 7 à v, on obtient (3, -4) : 84 3 + 60 (-4) = 252 - 240 = 12 ✓. C'est ce qui donnera l'ensemble des solutions au 37008. Ne pas calculer les produits pendant la remontée : Écrire 12 = 60 - 2 84 + 2 60 en gardant 84 et 60 APPARENTS est ce qui permet de regrouper. Calculer 2 84 = 168 au passage fait perdre la structure, et l'on ne retrouve plus u et v. Toujours vérifier le couple obtenu : La remontée enchaîne substitution, développement et regroupement : trois occasions de se tromper de signe. Un seul produit et une addition suffisent à contrôler — c'est le meilleur rapport sûreté / effort du chapitre.