Algorithme d'Euclide

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme d'Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d'Euclide.

Description[modifier | modifier le code]

Explications géométriques[modifier | modifier le code]

Dans la tradition grecque, en comprenant un nombre entier comme une longueur, 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.

Euclide2115.svg

Dans le rectangle de dimensions L=21 par l=15 ci-dessous, par exemple, on peut glisser un carré de côté 15 mais il reste un rectangle de côtés 15 et 6, dans lequel on peut 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.

Explications arithmétiques[modifier | modifier le code]

On considère que pgcd(a,0) = a et que pour b ≠ 0 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.

Généralisation[modifier | modifier le code]

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 à bien 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.

Remarque préliminaire[modifier | modifier le code]

Puisque l'algorithme a pour objet le calcul d'un PGCD, il est possible de se restreindre aux entiers positifs, un PGCD de deux entiers relatifs étant égal au PGCD de leurs valeurs absolues.

Description de l'algorithme[modifier | modifier le code]

Soient deux entiers naturels a et b, dont on cherche le PGCD. Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut. Une suite d'entiers (an)n est définie par récurrence de pas 2, plus précisément par divisions euclidiennes successives ; la suite est initialisée par a0 = a, a1 = b, puis propagée par la règle de récurrence : tant que an+1 est non nul, an+2 est défini comme le reste de la division euclidienne de an par an+1.

On commence donc par calculer le reste de la division de a par b, qu'on note r ; puis on remplace a par b, puis b par r, et on réapplique le procédé depuis le début.

On obtient ainsi une suite, qui vaut 0 à un certain rang ; le PGCD cherché est le terme précédent de la suite.

Si a < b, la première itération de la boucle a pour effet de "permuter a et b". Plus précisément : dans ce cas, la division euclidienne de a par b s'écrit a = b.0 + a donc a2 = a, si bien que la suite produite par l'algorithme appliqué au couple (a, b) commence par a, suivie de la suite produite par l'algorithme appliqué au couple (b, a).

Exemple[modifier | modifier le code]

PGCD.png

Calculons, par exemple, le PGCD de 1071 et de 1029 à l'aide de l'algorithme d'Euclide :

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 2 + 0

Il faut prendre le dernier reste avant le zéro, donc PGCD(1071 ; 1029) = 21

Remarque historique[modifier | modifier le code]

Au début, Euclide a formulé le 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é.

Démonstration de sa finitude et de son exactitude[modifier | modifier le code]

La définition même de la suite (a_n) par division euclidienne montre que, pour tout n tel que a_{n+1} est non nul, il existe un entier q_{n+2} tel que :  a_{n}=q_{n+2}\times a_{n+1}+a_{n+2}

avec de plus 0\leq a_{n+2}<a_{n+1} pour tout n tel que a_{n+1} non nul. La suite d'entiers naturels (a_n) est donc strictement décroissante (tant qu'elle est non nulle) à partir du rang 1, et donc vaut 0 à un certain rang. L'existence d'un dernier reste non nul est ainsi établie.

Soit N+1 l'indice de ce dernier reste non nul. Il faut montrer que a_{N+1} est bien le PGCD cherché. La relation précédente s'écrit donc ici a_N=q_{N+2}\times a_{N+1}, qui montre que a_{N+1} divise a_N. Écrivant ensuite a_{N-1}=q_{N+1}\times a_N+a_{N+1}, on en déduit que a_{N+1} divise aussi a_{N-1} ; puis, de même, et par récurrence, que a_{N+1} divise tous les termes de la suite a_n ; en particulier les premiers termes a et b. a_{N+1} est donc bien un diviseur commun de a et b. Réciproquement, tout diviseur commun de a et b divisera aussi a_2=a-q_2\times b, et à nouveau par récurrence, divisera tous les termes de la suite (a_n) ; donc en particulier a_{N+1}.

a_{N+1} est donc un diviseur commun de a et b que divise tout autre diviseur commun ; c'est bien le PGCD.

Le théorème de Lamé[modifier | modifier le code]

Le théorème de Lamé stipule que le nombre d'étapes de l'algorithme d'Euclide exécuté sur deux entiers est borné (supérieurement) par cinq fois le nombre de chiffres nécessaire à écrire (en base 10) le plus petit de ces deux entiers.

On peut en fait être légèrement plus précis : le nombre d'étapes de l'algorithme d'Euclide exécuté sur deux entiers a et b, avec b\leq a, est borné par la partie entière de \ln(b)/\ln(\varphi), où \ln désigne le logarithme naturel et \varphi est le nombre d'or.

Comme le nombre de chiffres de l'écriture de b en base 10 est \ln(b)/\ln(10) et que la quantité \ln(10)/\ln(\varphi) est inférieure à 5 (elle vaut environ 4,78497), on retrouve bien le théorème de Lamé.

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

Algorithme étendu aux coefficients de Bézout[modifier | modifier le code]

Article détaillé : Algorithme d'Euclide étendu.

Le théorème de Bachet-Bézout assure l'existence de deux entiers u et v tels que : au+bv=a_{N+1}=PGCD(a,b). L'algorithme d'Euclide convenablement adapté permet de calculer de tels coefficients.

Description[modifier | modifier le code]

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. Si de telles suites existent, les termes u_{N+1},v_{N+1} constitueront une paire de coefficients de Bézout pour a et b.

On peut choisir u_0=1, v_0=0 puis u_1=0,v_1=1, puis la relation de récurrence de pas 2 entre les a_n montre :

 a_{n+2}=a_n-q_{n+2}a_{n+1}
=au_n+bv_n-q_{n+2}(au_{n+1}+bv_{n+1})
=a(u_n-q_{n+2}u_{n+1})+b(v_n-q_{n+2}v_{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+2}u_{n+1} et l'initialisation précédente, et (v_n) par v_{n+2}=v_n-q_{n+2}v_{n+1} et l'initialisation précédente ; et on obtient bien la relation annoncée pour tout n.

Commentaires[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : fraction continue.

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 = 1071 et b = 1029 utilisé ci-dessus.

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

1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0

De cela on tire :

\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}}.

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

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

  • \frac{1071}{1029} \simeq \mathbf{1} = \frac{1}{1}
  • \frac{1071}{1029} \simeq \mathbf{1} + \frac{1}{\mathbf{24}} = \frac{25}{24}
  • \frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}} = \frac{51}{49}

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 se termine pas et la suite des approximations obtenues est donc elle-même infinie !

nota : La décomposition en fraction continuée (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).

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Lemme d'Euclide

Lien externe[modifier | modifier le code]

Calcul graphique du PGCD avec Geoplan (Java)