Entraînement
L'algorithme d'Euclide pour déterminer le pgcd de deux entiers
Signaler
Apprends à appliquer ton cours pour déterminer le pgcd de deux entiers. Toutes les étapes sont expliquées.
Mots clés : algorithme d'Euclide, PGCD
Énoncé
Déterminez le PGCD de 7830 et 12818 par l'algorithme d'Euclide
Révéler le corrigé
Révéler le corrigé
L'algorithme par divisions encore appelé algorithme d'Euclide repose sur la propriété suivante :
« a et b étant deux nombres entiers positifs tels que, on a PGCD (a ; b) = PGCD(b ; reste de a : b) »
Nous allons donc appliquer cette propriété pas à pas et présenter les résultats dans un tableau.
On effectue successivement les divisions euclidiennes et on note les restes successifs .
PGCD (12818 ; 7830) = PGCD(696 ; 58) = 58
Remarque :
Le PGCD(1281 ; 7830) est le dernier reste non nul obtenu dans l'algorithme d'Euclide donc
PGCD(7830 ; 1281) = 58
