PGCD et algorithme d'Euclide - cours

Le terme PGCD désigne le Plus Grand Commun Diviseur de deux nombres entiers positifs.

Il y a deux façons de procéder pour rechercher le PGCD de deux nombres a et b: la décomposition en produit de facteurs premiers et l'algorithme d'Euclide

L'algorithme d'Euclide, consiste à effectuer une suite de divisions euclidiennes :

- On effectue la division euclidienne de a par b et on note r le reste.

- Ensuite, b devient a et rdevient b comme sur le tableau ci-dessous; et on recommence: on effectue ladivision euclidienne de a par b et on note r le reste.

- Et on continue ainsi de suite jusqu'à ce qu'une division donne un reste égal à 0.

Dans cette méthode le PGCD est le dernier reste non nul.

Le reste est 0, on en déduit que 2 est le PGCD de 10 et de 8.

Il peut arriver qu'à un moment le reste soit 1 : dans ce cas, le PGCD est 1
(le reste suivant sera forcément zéro !)

Exemple : Déterminer le PGCDde 7 et de 4.

Consigne : Déterminer le PGCD des deux nombres de chaque question.

Intermédiaire Tweeter Partager
Exercice de maths (mathématiques) "PGCD et algorithme d'Euclide - cours" créé par anonyme avec le générateur de tests - créez votre propre test !
Voir les statistiques de réussite de ce test de maths (mathématiques)

Merci de vous connecter au club pour sauvegarder votre résultat.

98 et 109

55 et 65

118 et 1 098

1 279 et 1219

1 520 et 1 650

1 789 et 1 810

528 et 512

98 et 245

1 020 et 3 060

952 000 et 525