Algorithme d'Euclide

En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule efficacement le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, c'est-à-dire qu'ils sont tous les deux multiples de celui-ci. C'est un des plus anciens algorithmes connus, mais il reste toujours d'actualité.

L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres.

Histoire vignette|Peinture censée représenter le mathématicien Euclide d'Alexandrie, par le peintre Joos van Wassenhove.

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 ) 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 se 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 )... 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. Au , le mathématicien et astronome indien Aryabhata a décrit cet algorithme comme le « pulvérisateur »., à cause de son efficacité pour résoudre les équations diophantiennes..

Présentation Le PGCD (plus grand commun diviseur) de deux entiers relatifs est égal au PGCD de leurs valeurs absolues. De ce fait, on se restreint dans cette section aux entiers positifs.

Algorithme original (par différences successives) L'algorithme part du constat suivant : le PGCD de deux nombres n'est pas changé si on remplace le plus grand d'entre eux par leur différence. Autrement dit, . Par exemple, le PGCD de 21 et 15 est aussi égal au PGCD de 21 - 15 = 6 et 15. Puis, le PGCD de 6 et 15 est égal au PGCD de 15 - 6 = 9 et 6. Le tableau suivant contient les valeurs successives des deux nombres afin de calculer le PGCD de 21 et 15 : +ÉtapesPremier nombreDeuxième nombre étape2115 étape21 – 15 = 615 étape615 – 6 = 9 étape69 – 6 = 3 étape6 – 3 = 33 On s'arrête lorsque les deux nombres sont égaux : dans l'exemple, on est arrivé à 3. Ce nombre est le PGCD des deux nombres à chaque ligne, en particulier des deux nombres initiaux (sur l'exemple 21 et 15). Ce processus se termine toujours car le remplacement de ces nombres diminue strictement le plus grand d'entre eux.

Algorithme standard (par division euclidienne) On peut utiliser un raccourci en remplaçant des soustractions successives par une division euclidienne. Par exemple, on peut remplacer les soustractions successives : 15 – 6 = 9 9 – 6 = 3

par la division euclidienne de 15 par 6 qui donne 15 = 6 × 2 + 3. L'algorithme d'Euclide opère en utilisant ce raccourci : on remplace le plus grand des deux nombres par le reste de la division euclidienne du plus grand nombre par le plus petit. Ici, on remplace 15 par le reste 3. Dans Introduction à l'algorithmique de Cormen (voir Th. 31.9), les auteurs appellent théorème de la récursivité pour le PGCD le fait suivant :

où est le reste de la division euclidienne de par .

Une description précise de l'algorithme d'Euclide sur deux nombres entiers positifs et avec est donc : si , l'algorithme se termine et rend la valeur ; sinon, l'algorithme calcule le reste de la division euclidienne de par , puis recommence avec et .

Formellement l'algorithme d'Euclide construit une suite finie d'entiers par récurrence double :

, ; pour , est le reste de la division euclidienne de par , en particulier .

La suite est une suite strictement décroissante d'entiers positifs à partir du rang 1 : elle est donc finie et s'arrête au premier tel que .

Exemple Le tableau suivant montre le calcul du PGCD de 21 et 15. On réalise la division euclidienne de et : le quotient est 1 et le reste 6. L'algorithme continue avec et le précédent reste, jusqu'à trouver un reste nul. L'algorithme s'arrête alors et retourne le dernier reste non nul trouvé, ici qui est bien le PGCD de 21 et 15 : Étape Dividende Diviseur Équation Quotient Reste 1211521 = 15 × 1 + 616215615 = 6 × 2 + 3233636 = 3 × 2 + 020430fin de l'algorithme

Explications géométriques Dans la tradition grecque, en comprenant un nombre entier comme une longueur et un couple d'entiers comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul.

Considérons par exemple le rectangle de dimensions L = 21 par l = 15 représenté ci-dessous. On peut glisser un carré de côté 15 mais il reste un rectangle de côtés 15 et 6. On peut y glisser deux carrés de côté 6 mais il reste un rectangle de côtés 6 et 3 que l'on peut carreler entièrement de carrés de côté 3. Les carrés de côté 6 ou 15 peuvent aussi se carreler en carrés de côté 3. Le rectangle entier peut se carreler en carrés de côté 3. Il n'existe pas de carré plus grand permettant un tel carrelage. centré|vignette|782x782px|Explication géométrique de l'algorithme d'Euclide sur les entiers 21 et 15.

Implémentation Version itérative thumb|upright=2|Algorithme d'Euclide sous la forme d'un organigramme. On pose la question « est-ce que b = 0 ? ». Si oui, le pgcd est égal à a. Sinon, on part dans la boucle "Non". On revient à la question avec les nouvelles valeurs de a et b.Donald Knuth, dans , écrit une version itérative de l'algorithme d'Euclide. :

où l'on note a modulo b le reste de la division euclidienne de a et b.

La version originale de l'algorithme d'Euclide, où l'on n’effectue que des différences successives, est :

Version récursive Cormen , dans Introduction à l'algorithmique en donne une version récursive ; Dasgupta en donne la même version :

L'appel à euclide(a, b) s'arrête et retourne la valeur a si b = 0. Sinon, l'appel continue avec les nombres b et a modulo b. L'exécution du calcul de PGCD de 21 et 15 donne : .

Correction et terminaison On sait que et que . On progresse dans l'algorithme en diminuant à chaque étape les nombres considérés par calcul du modulo. L'algorithme se termine bien : pour une valeur non nulle de b, le calcul de PGCD(a, b) fait appel au calcul de PGCD(a’, b’), où 0 ≤ b’ < |b|, car b’ est le reste d'une division euclidienne par b.

Complexité vignette|Nombre d'étapes de l'algorithme d'Euclide en fonction des nombres entiers a et b (respectivement en abscisse et en ordonnées). Plus le point de coordonnées (a, b) est foncé, plus le calcul de PGCD(a, b) nécessite d'étapes. Les points (a, b) avec a > b les plus foncés sont concentrés autour de la droite a = bφ, où φ est le nombre d'or. Dans cette section, nous étudions la complexité temporelle de l'algorithme d'Euclide, c'est-à-dire le nombre d'étapes de calcul en fonction des entiers a et b. La première analyse de complexité connue est due à A. L. Reynaud en 1811 : il écrit que le nombre d'étapes de l'algorithme d'Euclide sur a et b est borné par b, . As cited by .. En 1841, P.-J.-E. Finck démontre que le nombre d'étapes est borné par 2 log2 b + 1. Cela démontre que l'algorithme d'Euclide s'exécute en temps polynomial en la taille de l'entrée (nombre de chiffres pour écrire les nombres a et b). En 1844, Gabriel Lamé raffine les résultats de Finck : il démontre que l'algorithme effectue au plus 5 fois le nombre de chiffres en base 10 du plus petit nombre.

Première analyse Nous donnons d'abord une analyse qui part du constat suivant : Si a ≥ b, alors a mod b < a / 2 Ainsi, si a et b sont codés sur n bits, au bout de deux appels récursifs, leur taille contient un bit de moins. Il y a donc O(n) appels récursifs. Comme la division euclidienne s'exécute en O(n2) opérations, l'algorithme d'Euclide est en O(n3).

Analyse via le théorème de Lamé La précédente analyse permet de montrer rapidement que l'algorithme d'Euclide est en O(log2(b)) divisions. Une analyse plus fineDétaillée par exemple dans ., due pour l'essentiel à Lamé, permet une meilleure évaluation (c'est la constante pour cette évaluation en O(log2(b)) qui peut être améliorée). Elle utilise la suite de Fibonacci définie par F0 = 0, F1 = 1, Fk+2 = Fk+1 + Fk, pour tout k ≥ 0, et dont les premiers termes sont : ...01123581321345589144233377610987... Quand l'algorithme d'Euclide est appelé sur deux nombres de Fibonacci consécutifs Fk+2 et Fk+1 , il utilise k appels récursifs : euclide( Fk+2 , Fk+1 ) = euclide( Fk+1 , Fk ) = ... euclide(F2, F1) = euclide(F1, F0) et comme pour chaque division euclidienne invoquée par l'algorithme le quotient est 1, cette situation est la pire du point de vue de la complexité, plus précisément on a le théorème de Lamé, Th. 31.11 :

On suppose sans perte de généralité que a > b (si a < b, l'algorithme échange a et b, si a = b, alors l'algorithme s'arrête en une étape). On démontre par récurrence sur k que si on effectue plus de k appels récursifs alors a ≥ Fk+2 et b ≥ Fk+1, lemme 31.10..

Pour k = 1, si on effectue au moins un appel récursif, cela signifie que a > b ≥ 1 et donc a ≥ F2 et b ≥ F1. Supposons que la propriété est vraie pour k-1 et considérons a et b pour lesquelles l'algorithme effectue plus de k appels. L'algorithme effectue k-1 appels pour b et a mod b. Par hypothèse de récurrence, cela signifie que b ≥ Fk+1 et que a mod b ≥ Fk. Mais a ≥ b + (a mod b) ≥ Fk+1 + Fk = Fk+2.

Cette majoration est la meilleure possible, puisqu'elle est atteinte quand et sont deux nombres de Fibonacci consécutifs.

Via la formule de Binet, Fk est équivalent à où est le nombre d'or. Ainsi, on en déduit à nouveau que le nombre d'appels récursifs est . Plus précisément, il y a au plus appels récursifs, où désigne le logarithme en base . On peut même montrer qu'il y a , exercice 31.2.5..

Complexité quadratique Soit n le nombre de bits dans les nombres d'entrées. Comme l'algorithme effectue une division euclidienne à chaque appel récursif, qui coûte O(n2), et qu'il y a O(n) appels récursifs, l'algorithme est en O(n3). Toutefois, une analyse fine montre que l'algorithme s'exécute en temps quadratique en le nombre de bits des nombres d'entrées (voir Problème 31.2 laissé en exercice dans, p. 902).

Généralisation

Algorithme étendu aux coefficients de Bézout

Le théorème de Bachet-Bézout assure l'existence de deux entiers et tels que : . L'algorithme d'Euclide étendu calcule de tels coefficients.

Pour cela, on introduit deux suites et telles que pour tout , on ait la relation : où est la valeur de à la n-ième étape de l'algorithme. Les termes constitueront une paire de coefficients de Bézout pour et , où est le numéro de la dernière étape de l'algorithme.

On choisit et (afin que soit vrai pour et pour ), puis la relation de récurrence de pas 2 entre les montre :