Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme d'Euclide
Résumé
En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un reste nul. L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres.
vignette|Peinture censée représenter le mathématicien Euclide d'Alexandrie, par Justus of Ghent.
Selon Donald Knuth, l'algorithme d'Euclide est l'un des plus anciens algorithmes. Il est décrit dans le livre VII (Proposition 1-3) des Éléments d'Euclide (vers 300 av. J.-C.) sous la forme de l'anthyphérèse. Il est aussi décrit dans le livre X (Proposition 2), mais pour un problème de façon géométrique : comment trouver une « unité de mesure » commune pour deux longueurs de segments. Il procède par soustractions répétées de la longueur du plus court segment sur la longueur du plus long. Cela correspond à une adaptation de la méthode naïve de calcul de la division euclidienne, telle que décrite dans l'article consacré. Pour ce problème géométrique, l'algorithme d'Euclide ne termine pas forcément (dans un langage plus moderne, cela correspond à exécuter l'algorithme d'Euclide pour des nombres réels).
L'algorithme n'a probablement pas été découvert par Euclide, qui aurait compilé des résultats d'autres mathématiciens dans ses Éléments. Pour le mathématicien et historien B. L. van der Waerden, le livre VII vient d'un livre de théorie des nombres écrit par un mathématicien de l'école de Pythagore L'algorithme était probablement connu d'Eudoxe de Cnide (vers 375 av. J.-C.). Il se peut même que l'algorithme ait existé avant Eudoxe, vu les termes techniques ἀνθυφαίρεσις (anthyphairesis, soustraction réciproque) dans les travaux d'Euclide et aussi d'Aristote.
Quelques siècles plus tard, l'algorithme d'Euclide est inventé de manière indépendante à la fois en Inde et en Chine. L'objectif était de résoudre des équations diophantiennes issues de l'astronomie et de faire des calendriers plus précis.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.