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 a vu que PGCD(84, 60) = 12. Remontons les divisions :
2. Étape 2 : 24 = 84 - 60 1
3. Étape 3 : 12 = 60 - 24 2 = 60 - 2(84 - 60) = -2 84 + 3 60
4. Étape 4 : Donc u = -2 et v = 3 : 84 (-2) + 60 3 = -168 + 180 = 12 ✓

   84 (-2) + 60 3 = 12