Exercice 25

Calculer le PGCD de 126 et 180.

Réponse

\(\gcd(126,180)=18\)

Corrigé détaillé

Définition du PGCD

Le plus grand commun diviseur (PGCD) de deux nombres entiers est le plus grand entier qui divise chacun d’eux sans laisser de reste.

1. Principe de l’algorithme d’Euclide

L’algorithme d’Euclide consiste à réaliser des divisions successives et à retenir à chaque étape le reste de la division. Quand le reste devient zéro, le PGCD est le dernier reste non nul.

2. Application à 126 et 180

1. Division de 180 par 126 :
   • Quotient : 1
   • Reste : 54
   • On vérifie avec la formule \(180 = 126 \times 1 + 54\).
2. Division de 126 par 54 :
   • Quotient : 2
   • Reste : 18
   • Vérification : \(126 = 54 \times 2 + 18\).
3. Division de 54 par 18 :
   • Quotient : 3
   • Reste : 0
   • Vérification : \(54 = 18 \times 3 + 0\).

3. Conclusion

Comme le reste devient nul à la troisième étape, le PGCD de 126 et 180 est le dernier reste non nul, soit 18. Ainsi

\[ \gcd(126,180)=18. \]