Algorithme d'Euclide

L'algorithme d'Euclide est un algorithme servant à déterminer le plus grand commun diviseur de deux entiers dont on ne connaît pas la factorisation.



Catégories :

Théorie algorithmique des nombres - Algorithme numérique

Recherche sur Google Images :


Source image : geombre.com
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • ALGORITHME d'EUCLIDE. 1.2.4.5.8.10. AUTO. Côté d'un carreau. Entrer deux nombres entiers inférieurs à 73. Premier nombre. Deuxième nombre... (source : pagesperso-orange)
  • L'algorithme d'Euclide est une méthode pour trouver quasiment le PGCD de deux... d'Euclide sert à calculer une valeur envisageable pour ces entiers u et v.... en exprimant le pgcd d suivant les autres nombres, en premier lieu dans la... (source : bibmath)
  • Calcul du pgcd de deux entiers. L'algorithme d'Euclide sert à calculer le pgcd de deux nombres entiers. L'al- gorithme consiste `a construire une suite... (source : math.u-psud)

L'algorithme d'Euclide est un algorithme servant à 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.

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é servant à 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 qu'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 donnant la possibilité un tel carrelage.

Cet algorithme repose sur la structure d'anneau euclidien de l'anneau \mathbb{Z} des entiers relatifs, surtout sur la propriété de division euclidienne. Il se généralise par conséquent à bien d'autres anneaux, surtout les anneaux de polynômes à cœfficients dans un corps. L'algorithme se généralise pour permettre le calcul des cœfficients de Bezout.

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, surtout, en algèbre linéaire, le calcul de facteurs invariants.

Remarque préliminaire

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

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 exactement 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 débute par conséquent 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 dernier reste non nul.

Exemple

PGCD.png

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

1071 = 1029 x 1 + 42

1029 = 42 x 24 + 21

42 = 21 x 2 + 0

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

Pseudocode récursif

Fonction PGCD (a :nombre, b :nombre)  :nombre

Si b=0
| alors PGCD=a
Sinon
| r egal au reste de la division entière (modulo) de a par b
| PGCD=PGCD(b, r)

Ce qui pourrait donner en C :

int PGCD(int a, int b) {
   return b ? PGCD(b, a%b):a;
}

Remarque historique

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

La définition même de la suite (an) par division euclidienne montre que, pour tout n tel que an + 1 est non nul, il existe un entier qn + 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}. La suite d'entiers naturels (an) est par conséquent strictement décroissante, et par conséquent 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 aN + 1 est bien le PGCD cherché. La relation précédente s'écrit par conséquent ici a_N=q_{N+2}\times a_{N+1}, qui montre que aN + 1 divise aN. Écrivant ensuite a_{N-1}=q_{N+1}\times a_N+a_{N+1}, on en déduit que aN + 1 divise aussi aN − 1 ; puis, de même, et par récurrence, que aN + 1 divise l'ensemble des termes de la suite an ; surtout les premiers termes a et b. aN + 1 est par conséquent 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, ainsi qu'à nouveau par récurrence, divisera l'ensemble des termes de la suite (an)  ; par conséquent surtout aN + 1.

aN + 1 est par conséquent un diviseur commun de a et b que divise tout autre diviseur commun ; c'est bien le PGCD.

Le théorème de Lamé

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

On peut en fait être un peu plus précis : le nombre d'étapes de l'algorithme d'Euclide exécuté sur deux entiers a et b, avec a\leq b, est borné par la partie entière de \ln(b)/\ln(\varphi), où ln sert à désigner 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 à peu près 4, 78497), on retrouve bien le théorème de Lamé.

De plus, cette limite supérieure est la meilleure envisageable, dans la mesure où elle est atteinte lorsque a et b sont deux nombres de Fibonacci consécutifs.

Algorithme étendu aux cœfficients de Bézout

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

L'identité de Bézout assure l'existence de deux entiers u et v tels que : au + bv = aN + 1 = PGCD (a, b) . L'algorithme d'Euclide convenablement adapté sert à calculer de tels cœfficients.

Pour cela, on introduit deux suites (un) et (vn) telles que pour tout n, on ait la relation : aun + bvn = an. Si de telles suites existent, les termes uN + 1, vN + 1 formeront une paire de cœfficients de Bezout pour a et b.

On peut choisir u0 = 1, v0 = 0 puis u1 = 0, v1 = 1, puis la relation de récurrence de pas 2 entre les an montre :

an + 2 = anqn + 2an + 1 = aun + bvnqn + 2 (aun + 1 + bvn + 1) = a (unqn + 2un + 1) + b (vnqn + 2vn + 1)

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

Commentaires

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

Fractions continues

Article détaillé : fraction continue.

Les quotients successifs qui apparaissent lorsque l'algorithme d'Euclide est appliqué aux données a et b, sont exactement 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 se nomme 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 :

Cette méthode peut aussi ê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 apporte 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 par conséquent elle-même illimitée !

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, ainsi qu'à 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 apporte un polynôme qui exécute une approximation de la fonction. Mais on peut aussi chercher une fraction rationnelle qui satisfasse les mêmes conditions que la partie polynômiale 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 sert à très intéressants développements (voir par exemple la démonstration de l'irrationalité de ζ (3) ).

Voir aussi

Liens externes

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu