La division euclidienne et le PGCD
Diviser, trouver le PGCD, simplifier.
Algorithmus Euclidis
L'algorithme d'Euclide
Euclide enseigne dans ses « Éléments » (Livre VII) que tout nombre peut être divisé par un autre, donnant un quotient et un reste. Cette « division euclidienne » est le fondement de l'art du calcul. Plus remarquable encore, Euclide propose un algorithme pour trouver la « plus grande commune mesure » de deux nombres, ce que nous appelons le PGCD. Ce procédé, transmis par Boèce à nos écoles, repose sur des divisions successives: on divise le plus grand par le plus petit, puis le diviseur par le reste, et ainsi de suite jusqu'à obtenir un reste nul. Le dernier diviseur non nul est la commune mesure cherchée.
Exemples et nombres premiers
Prenons quelques exemples pour affermir la compréhension de ces principes. Si l'on divise 17 par 5, on obtient un quotient de 3 et un reste de 2, puisque 5 multiplié par 3 donne 15, et qu'il reste 2 pour atteindre 17. Appliquons maintenant l'algorithme d'Euclide pour trouver le PGCD de 12 et 8: on divise 12 par 8, quotient 1, reste 4; puis 8 par 4, quotient 2, reste 0. Le dernier diviseur non nul est 4, c'est la plus grande commune mesure de 12 et 8. De même, pour 15 et 25: on divise 25 par 15, reste 10; puis 15 par 10, reste 5; puis 10 par 5, reste 0. Le PGCD est donc 5. Un cas particulier mérite attention: lorsque deux nombres n'ont d'autre commune mesure que l'unité, on les dit « premiers entre eux ». Ainsi 8 et 15 sont premiers entre eux, car en appliquant l'algorithme on aboutit à un PGCD de 1, ces deux nombres ne partagent aucun diviseur commun hormis 1, bien que ni l'un ni l'autre ne soit un nombre premier en soi. Les Éléments d'Euclide, transmis à l'Occident latin principalement par Boèce dans son De Institutione Arithmetica, demeurent la source de cet enseignement fondamental de l'arithmétique.
Le dernier diviseur non nul est la commune mesure cherchée.
Testez-vous : 8 questions
1. Que donne la division euclidienne de 17 par 5 ?
- Quotient 2, reste 7
- Quotient 4, reste 1
- Quotient 3, reste 2
- Quotient 3, reste 3
Voir la réponse
Réponse : Quotient 3, reste 2
La division euclidienne de 17 par 5 donne : 17 = 5 × 3 + 2, soit un quotient de 3 et un reste de 2. L’algorithme d’Euclide, fondé sur cette division, permet de trouver le PGCD de deux nombres par divisions successives.
2. Quel mathématicien de l’Antiquité a formulé l’algorithme pour trouver la plus grande commune mesure de deux nombres ?
- Euclide
- Pythagore
- Archimède
- Thalès
Voir la réponse
Réponse : Euclide
Euclide formula dans les Éléments (livre VII, propositions 1-2) l’algorithme de division successive pour trouver la plus grande commune mesure (PGCD) de deux nombres. Cet « algorithme d’Euclide », l’un des plus anciens de l’histoire, est encore utilisé aujourd’hui.
3. Quel est le PGCD de 12 et 8, c’est-à-dire le plus grand nombre qui divise les deux ?
- 8
- 6
- 2
- 4
Voir la réponse
Réponse : 4
Le PGCD de 12 et 8 est 4. Par l’algorithme d’Euclide : 12 = 1 × 8 + 4, puis 8 = 2 × 4 + 0. Le dernier reste non nul est 4, qui est le plus grand diviseur commun. On vérifie : 12/4 = 3 et 8/4 = 2, nombres premiers entre eux.
4. Dans l’algorithme d’Euclide, quand s’arrête-t-on ?
- En trouvant un pair
- Si le quotient vaut 1
- Après trois divisions
- Quand le reste est nul
Voir la réponse
Réponse : Quand le reste est nul
Dans l’algorithme d’Euclide, on s’arrête quand le reste de la division est nul. Le dernier reste non nul est alors le PGCD des deux nombres. Par exemple, pour PGCD(12, 8) : 12 = 1×8 + 4, puis 8 = 2×4 + 0. Le reste est 0, donc le PGCD est 4.
5. Euclide expose son algorithme de la commune mesure dans quel ouvrage ?
- L’Arénaire
- Les Éléments
- Les Coniques
- L’Almageste
Voir la réponse
Réponse : Les Éléments
Euclide expose son algorithme de la commune mesure (PGCD) dans les Éléments. Boèce transmit cet ouvrage au Moyen Âge latin.
6. Quel est le PGCD de 15 et 25, trouvé par divisions successives ?
- 10
- 3
- 15
- 5
Voir la réponse
Réponse : 5
Par l’algorithme d’Euclide : 25 = 1 × 15 + 10, puis 15 = 1 × 10 + 5, puis 10 = 2 × 5 + 0. Le dernier reste non nul est 5, donc PGCD(15, 25) = 5. Ce procédé de divisions successives, décrit dans les Éléments d’Euclide, est l’un des plus anciens algorithmes connus.
7. Deux nombres dont le PGCD est 1 sont dits « premiers entre eux ». Quel couple est premier entre eux ?
- 12 et 18
- 8 et 15
- 10 et 25
- 6 et 9
Voir la réponse
Réponse : 8 et 15
Deux nombres sont premiers entre eux (copremiers) quand leur PGCD est 1. Pour 8 (= 2³) et 15 (= 3 × 5), ils ne partagent aucun facteur premier commun, donc PGCD(8, 15) = 1. Ils sont bien premiers entre eux, même si ni 8 ni 15 ne sont des nombres premiers.
8. Par quel auteur latin l’algorithme d’Euclide fut-il principalement transmis à nos écoles d’Occident ?
- Isidore de Séville
- Cassiodore
- Alcuin
- Boèce
Voir la réponse
Réponse : Boèce
L’algorithme d’Euclide pour trouver le PGCD fut principalement transmis aux écoles d’Occident par Boèce, dans son De Institutione Arithmetica. Ce traité, adaptation latine de Nicomaque de Gérase, fut le manuel d’arithmétique de référence pendant près de mille ans.
Faites cette leçon dans Apôtre : les questions en mode interactif, votre progression, des rappels pour ne rien oublier. Gratuit, sans publicité. Commencer la leçon ›