Entrer a: Entrer b:
Selon Donald Knuth, l'algorithme d'Euclide est l'un des plus anciens algorithmes1. Il est décrit dans le livre VII (Proposition 1-3) des Éléments d'Euclide (vers 300 avant JC) 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).
Probalement, l'algorithme n'as pas été découvert par Euclide, qui aurait compilé des résultats d'autres mathématiciens dans ses Elements2,3. Pour le mathématicien et historienn 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 Pythagore4 L'algorithme était probablement connu de Eudoxe de Cnide (vers 375 avant JC)5,6. Il se peut même que l'algorithme aurait existé avant Eudoxe7,8, vu les termes techniques ἀνθυφαίρεσις (anthyphairesis, soustraction réciproque) dans les travaux d'Euclide et aussi d'Aristote9.
Quelques siècles plus tard, l'algorithme d'Euclide est inventé de manière indépendante à la fois en Inde et en Chine (voir p. 31 dans 10). L'objectif était de résoudre des équations diophantiennes issus de l'astronomie et de faire des calendriers plus précis. Au 5e siècle, le mathématicien et astronome indien Aryabhata a décrit cette algorithme comme le "pulvérisateur" (voir p. 70 de 11), à cause de son efficacité pour résoudre les équations diophantiennes (voir p. 86-87 dans 12).