PGCD par algorithme d'Euclide

Énoncé

Calculer PGCD(84, 60) en utilisant l'algorithme d'Euclide.

Indice : Effectue des divisions euclidiennes successives jusqu'à obtenir un reste nul.

Correction

1. Étape 1 : L'algorithme d'Euclide repose sur une seule idée, qu'il faut avoir vue une fois : Le principe : Si a = bq + r, alors PGCD(a, b) = PGCD(b, r). Pourquoi ? Parce que tout diviseur commun à a et b divise r = a - bq, et réciproquement tout diviseur commun à b et r divise a = bq + r. Les deux couples ont donc exactement les mêmes diviseurs communs.
2. Étape 2 : Première division :

   84 = 60 1 + 24 PGCD(84,60) = PGCD(60,24)

3. Étape 3 : Deuxième :

   60 = 24 2 + 12 PGCD(60,24) = PGCD(24,12)

4. Étape 4 : Troisième, où le reste devient nul :

   24 = 12 2 + 0 PGCD(24,12) = 12

5. Étape 5 : Le dernier reste NON NUL est le PGCD :

   PGCD(84,60) = 12

6. Étape 6 : Contrôle par décomposition. 84 = 2^2 3 7 et 60 = 2^2 3 5. Les facteurs communs sont 2^2 3 = 12 ✓. Cette voie est plus lente sur de grands nombres, mais elle confirme ici en trois secondes. C'est le dernier reste NON NUL, pas le dernier reste : Le dernier reste est toujours 0 — c'est ce qui arrête l'algorithme. Le PGCD est celui d'AVANT, ici 12. Répondre 0 est l'erreur d'inattention classique. Garder les divisions écrites : Elles serviront telles quelles à l'exercice 37007, où l'on remonte l'algorithme pour obtenir les coefficients de Bézout. Les effacer oblige à tout refaire.