Algorithme d'Euclide

Principe

Le PGCD de deux entiers relatifs est égal au PGCD de leurs valeurs absolues : de ce fait, on se restreint dans cette section aux entiers positifs. 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, pgcd(a, b) = pgcd(a−b, b). Par exemple, le PGCD de 252 et 105 vaut 21, mais c'est aussi le PGCD de 252 − 105 = 147 et 105. Ainsi, comme le remplacement de ces nombres diminue strictement le plus grand d'entre eux, on peut continuer le processus, jusqu'à obtenir deux nombres égaux.

Dans l'algorithme, on pourrait réaliser autant de différences que l'on souhaite. Par exemple, le PGCD de 252 et 105 est aussi égal au PGCD de 105 et 252 − 2 × 105 = 42. Ainsi, l'algorithme d'Euclide opère ainsi : on remplace le plus grand des deux nombres par le reste de la division euclidienne du plus grand nombre par le plus petit. Par exemple, la division euclidienne de 252 par 105 donne un reste de 42. Dans Introduction à l'algorithmique de Cormen et al. (voir Th. 31.9), les auteurs appellent théorème de la récursivité pour le PGCD le fait suivant :

pgcd(a, b) = pgcd(b, r) où r est le reste de la division euclidienne de a par b.

Ainsi, l'algorithme d'Euclide sur deux nombres entiers positifs a et b avec a > b ⩾ 0 procède comme suit :

• si b = 0, l'algorithme termine et rend la valeur a ;
• sinon, l'algorithme calcule le reste r de la division euclidienne de a par b, puis recommence avec a := b et b := r.

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

• r₀ = a, r₁ = b ;
• pour n ⩾ 1, r_n+1 est le reste de la division euclidienne de r_n-1 par r_n, en particulier r_n+1 < r_n.

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

Exemple

Le tableau suivant montre le calcul du PGCD de 21 et 15. On réalise la division euclidienne de a = 21 et b = 15 : le quotient est 1 et le reste 6. L'algorithme continue avec a := b et b := 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 $r_3=3$ qui est bien le PGCD de 21 et 15 :

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.

Version itérative

Donald Knuth, dans The Art of Computer Programming, é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 et al., dans Introduction à l'algorithmique en donne une version récursive ; Dasgupta et al. 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 : euclide(21, 15) = euclide(15, 6) = euclide(6, 3) = euclide(3, 0) = 3.

Correction et terminaison

On sait que PGCD(a, 0) = a et que PGCD(a, b) = PGCD(b, a mod b). On progresse dans l'algorithme en diminuant à chaque étape les nombres considérés par calcul du modulo. L'algorithme 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.

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, leurs tailles contient un bit de moins. Il y a donc O(n) appels récursifs. Comme la division euclidienne s'exécute en O(n) opérations, l'algorithme d'Euclide est en O(n).

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(log₂(b)) divisions. Une analyse plus fine, due pour l'essentiel à Lamé, permet une meilleure évaluation (c'est la constante pour cette évaluation en O(log₂(b)) qui peut être améliorée). Elle utilise la suite de Fibonacci définie par

F₀ = 0, F₁ = 1, F_k+2 = F_k+1 + F_k, pour tout k ≥ 0,

et dont les premiers termes sont :

.

Quand l'algorithme d'Euclide est appelé sur deux nombres de Fibonacci consécutifs F_k+2 et F_k+1 , il utilise k appels récursifs :

euclide( F_k+2 , F_k+1 ) = euclide( F_k+1 , F_k ) = ... euclide(F₂, F₁) = euclide(F₁, F₀)

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é :

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

Via la formule de Binet, F_k est équivalent à $varphi ^k/sqrt 5$ où $varphi$ est le nombre d'or. Ainsi, on en déduit à nouveau que le nombre d'appels récursifs est $O(log(b))$. Plus précisément, il y a au plus $1+log _phi (b)$ appels récursifs, où $log _phi$désigne le logarithme en base $varphi$. On peut même montrer qu'il y a $1+log _phi (b/pgcd(a,b))$.

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(n), et qu'il y a O(n) appels récursifs, l'algorithme est en O(n). 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).

Anneau euclidien

Cet algorithme repose sur la structure d’anneau euclidien de l’anneau Z des entiers relatifs, plus particulièrement sur la propriété de division euclidienne. Il se généralise donc à d’autres anneaux, en particulier les anneaux de polynômes à coefficients dans un corps. L’algorithme se généralise pour permettre le calcul des coefficients de Bézout.

L’algorithme est effectif à condition de disposer d’un algorithme effectif de division euclidienne. La possibilité de disposer d’un tel algorithme rend de nombreux autres calculs effectifs, notamment, en algèbre linéaire, le calcul de facteurs invariants.

Algorithme étendu aux coefficients de Bézout

Le théorème de Bachet-Bézout assure l'existence de deux entiers u et v tels que : $au+bv=PGCD(a,b)$. L'algorithme d'Euclide étendu calcule de tels coefficients.

Pour cela, on introduit deux suites $(u_n)$ et $(v_n)$ telles que pour tout n, on ait la relation : $au_n+bv_n=a_n$où $a_n$est la valeur de $a$ à la nème étape de l'algorithme. Les termes $u_N,v_N$ constitueront une paire de coefficients de Bézout pour a et b, où N est le numéro de la dernière étape de l'algorithme.

On choisit $u_0=1,v_0=0$ et $u_1=0,v_1=1$ (afin que $au_n+bv_n=a_n$ soit vrai pour n = 0 et pour n = 1), puis la relation de récurrence de pas 2 entre les $a_n$ montre :

$a_n+2=a_n-q_n+2a_n+1=au_n+bv_n-q_n+2(au_n+1+bv_n+1)=a(u_n-q_n+2u_n+1)+b(v_n-q_n+2v_n+1)$

On peut ainsi définir $(u_n)$ par la relation de récurrence de pas 2 : $u_n+2=u_n-q_n+2u_n+1$ et l'initialisation précédente, et $(v_n)$ par $v_n+2=v_n-q_n+2v_n+1$ et l'initialisation précédente ; et on obtient bien la relation annoncée pour tout n.

L'algorithme étendu s'implémente comme l'algorithme classique ; il suffit de rajouter des variables correspondant aux coefficients u et v à calculer, et de faire une multiplication et une soustraction supplémentaires, pour calculer chacun des deux nouveaux coefficients, à chaque étape.

Fractions continues

Les quotients successifs qui apparaissent quand l'algorithme d'Euclide est appliqué aux données a et b, sont précisément les nombres qui apparaissent dans la représentation sous forme de fraction continue de a/b. Considérons l'exemple de a = 1 071 et b = 1 029 utilisé ci-dessus.

Voici le calcul avec les quotients soulignés (successivement 1, 24 et 2) :

1 071 = 1 029 × 1 + 42

1 029 = 42 × 24 + 21

42 = 21 × 2 + 0

De cela on tire :

$frac 10711029=mathbf 1 +frac 1mathbf 24 +frac 1mathbf 2$.

Dans l'égalité précédente, le second membre s'appelle la fraction continue ou continuée du quotient 1 071/1 029.

On peut en déduire les trois approximations suivantes de la fraction, classées par ordre de précision croissante :

• $frac 10711029simeq mathbf 1 =frac 11$ ;
• $frac 10711029simeq mathbf 1 +frac 1mathbf 24 =frac 2524$ ;
• $frac 10711029=mathbf 1 +frac 1mathbf 24 +frac 1mathbf 2 =frac 5149$.

Cette méthode peut également être utilisée pour des nombres réels a et b ; comme dans le cas de deux entiers, la suite de quotients calculés représente la « décomposition en fraction continue » de a/b et fournit une suite d'approximations successives, de qualité croissante, du quotient a/b. Dans le cas où ce quotient est irrationnel, l'algorithme d'Euclide ne termine pas et la suite des approximations obtenues est infinie.

Nota : La décomposition en fraction continue (et la série d'approximations successives correspondante) peut être appliquée, non seulement à un nombre réel quelconque, mais également à une fonction : cette démarche consiste à rechercher les approximants de Padé, dont on peut définir le principe comme suit : Au voisinage d'un point, le développement en série de Taylor d'une fonction donnée fournit un polynôme qui réalise une approximation de la fonction. Mais on peut également chercher une fraction rationnelle qui satisfasse les mêmes conditions que la partie polynomiale du développement de Taylor : l'égalité des dérivées de la fonction et de son approximation, jusqu'à un certain ordre donné.

La comparaison de ces deux types de développements permet de très intéressants développements, comme la démonstration de l'irrationalité de ζ(3)