L’algorithme d’Euclide : un calcul fondé sur le raisonnement

Si le nom d'EuclideEuclide est resté attaché à la géométrie et à la méthode axiomatique, il est aussi, ironiquement, resté associé à un algorithme qui permet de calculer le plus grand diviseur commun de deux nombres entiers : l'algorithme d'Euclide. Une première méthode pour calculer le plus grand diviseur commun de deux nombres consiste à déterminer les diviseurs de chacun d'eux en les divisant successivement par tous les nombres plus petits et en retenant ceux pour lesquels la division tombe juste. Par exemple, pour calculer le plus grand diviseur commun de 90 et 21, on peut déterminer les diviseurs de 90 (1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, et 90) et ceux de 21 (1, 3, 7 et 21) ; il ne reste plus qu'à chercher le plus grand nombre qui se trouve dans les deux listes : 3. Pour résoudre le problème « le plus grand diviseur commun de 90 et 21 est-il égal à 3 ? » ou même le problème « quel est le plus grand diviseur commun de 90 et 21 ? », il n'est donc nullement nécessaire de faire un raisonnement. Il suffit d'appliquer cet algorithme, laborieux mais systématique, qui est une simple paraphrase de la définition du plus grand diviseur commun.

L'algorithme d'Euclide permet de calculer de manière moins laborieuse le plus grand diviseur commun de deux nombres. Il repose sur l'idée suivante : quand on veut calculer le plus grand diviseur commun de deux nombres a et b, par exemple 90 et 21, on peut diviser le plus grand a par le plus petit b. Si la division « tombe juste » et donne un quotient q, alors a est égal b × q. Dans ce cas, b est un diviseur de a, donc un diviseur commun de a et b, et c'est le plus grand car aucun diviseur de b n'est plus grand que b lui-même. Ce nombre est donc le plus grand diviseur commun de a et b. Si, en revanche, la division ne « tombe pas juste » et laisse un reste r, alors a est égal à b × q + r ; dans ce cas, les diviseurs communs de a et b sont aussi ceux de b et r. De ce fait, on peut remplacer les nombres a et b par les nombres b et r qui ont même plus grand diviseur commun. L'algorithme d'Euclide consiste à répéter cette opération plusieurs fois jusqu'à obtenir deux nombres pour lequel la division tombe juste. Le nombre recherché est alors le plus petit des deux nombres. Calculer le plus grand diviseur des nombres 90 et 21 avec l'algorithme d'Euclide consiste à remplacer le couple (90, 21) par le couple (21, 6) puis par le couple (6, 3) et, 6 étant un multiple de 3, par le nombre 3 qui est le résultat.

Dans le cas des nombres 90 et 21, l'algorithme d'Euclide donne un résultat après trois divisions. Plus généralement, quels que soient les nombres avec lesquels on démarre, on obtient un résultat après un nombre fini de divisions. En effet, en remplaçant le nombre a par le nombre r, on fait décroître les nombres qui constituent le couple dont on cherche à calculer le plus grand diviseur commun, et une suite décroissante de nombres entiers est nécessairement finie.

Cet exemple montre que, loin de tourner le dosdos au concept de calcul, les Grecs, comme ici Euclide, ont participé à la constructionconstruction de nouveaux algorithmes. Il montre également à quel point le raisonnement et le calcul sont entremêlés dans la pratique mathématique. La construction de l'algorithme d'Euclide, contrairement au premier algorithme de calcul du plus grand diviseur commun, nous a demandé de démontrer plusieurs théorèmes : premièrement, si la division de a par b tombe juste, alors le plus grand diviseur commun de a et b est b ; deuxièmement, si r est le reste de la division de a par b, alors les diviseurs communs de a et b sont les mêmes que ceux de b et r ; troisièmement, le reste d'une division est toujours inférieur au diviseur ; enfin, une suite décroissante de nombres entiers est finie. Ces résultats sont établis par des raisonnements, similaires à ceux utilisés par les pythagoriciens pour démontrer qu'un carré ne peut pas être le double d'un autre.

La conception du premier algorithme ne demandait aucun raisonnement. Mais cette situation est exceptionnelle. En général, les algorithmes, comme celui d'Euclide, ne se contentent pas de paraphraser une définition et leur conception demande de construire un raisonnement.