> Plus de cours et d'exercices de maths (mathématiques) sur le même thème: Arithmétique [Autres thèmes]
	> Tests similaires: - Multiples de 2, 3, 5, 9 et 10 (CM2-6ème) - Critères de divisibilité par 2,3,4,5,8,9,11 - Additions à trous en base douze - PPCM-Plus Petit Multiple Commun - Bases - Jeu: Pyramide et additions en base douze - PGCD et nombres premiers entre eux - PGCD : cours
	> Double-cliquez sur n'importe quel terme pour obtenir une traduction...

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 r devient b comme sur le tableau ci-dessous; et on recommence: on effectue la division 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.

a désigne le plus grand nombre et b désigne le plus petit.

a	b	r
Le plus grand nombre	Le plus petit nombre	Le RESTE de la division euclidienne de a par b
10	8	2
8	2	0

Exemple du tableau : Déterminer le PGCD de 10 et de 8

10:8 = 1 reste 2

10 2	8
	1

8:2 = 4 reste 0

8 0	2
	4

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 PGCD de 7 et de 4.

a	b	r
Le plus grand nombre	Le plus petit nombre	Le RESTE de la division euclidienne de a par b
7	4	3
4	3	1

7:4 = 1 reste 3
4:3 = 1 reste 1
Le résultat est 1, le PGCD de 7 et de 4 est donc 1.

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

Intermédiaire
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) [Sauvegarder] [Charger] [?]

Si nécessaire, pour insérer facilement des caractères accentués et symboles mathématiques:


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