Algorithme d'Euclide 2012920 31608308 2008-07-15T20:46:20Z CarsracBot 400947 robot Ajoute: [[simple:Euclidean algorithm]] L''''algorithme d'Euclide''' est un [[Algorithmique|algorithme]] permettant de déterminer le [[PGCD|plus grand commun diviseur]] (P.G.C.D.) de deux [[entier relatif|entiers]] dont on ne connaît pas la [[décomposition en produit de facteurs premiers|factorisation]]. Il est déjà décrit dans le livre VII des ''[[Éléments d'Euclide|É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 taille du plus grand carré permettant de carreler 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. [[Image:EuclidePGCD.png]] Cet algorithme repose sur la structure d'[[anneau euclidien]] de l'[[anneau (mathématiques)|anneau]] <math>\mathbb{Z}</math> 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ôme]]s à coefficients dans un corps. L'algorithme se généralise pour permettre le calcul des [[identité de Bezout|coefficients 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, notamment, en algèbre linéaire, le calcul de [[Théorème des facteurs invariants|facteurs invariants]]. == Remarque préliminaire == Puisque l'algorithme a pour objet le calcul d'un PGCD, il est possible de se restreindre aux [[entiers naturels|entiers positifs]], un PGCD de deux entiers relatifs étant égal au PGCD de leurs valeurs absolues. == Description de l'algorithme == 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 <math>(a_n)_n</math> est définie par [[raisonnement par récurrence|récurrence]] de pas 2, plus précisément par divisions euclidiennes successives ; la suite est initialisée par <math>a_0=a, a_1=b</math>, puis propagée par la règle de récurrence : tant que <math>a_{n+1}</math> est non nul, <math>a_{n+2}</math> est défini comme le reste de la division euclidienne de <math>a_n</math> par <math>a_{n+1}</math>. 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 <math>0</math> à un certain rang ; le PGCD cherché est le dernier reste non nul. === Exemple === [[Image:PGCD.png|right]] Calculons, par exemple, le [[PGCD|pgcd]] de 1071 et 1029 (égal à 21) par cet algorithme avec les étapes suivantes : {| |----- | align="right" | ''a'' | align="right" | ''b'' | align="right" | ''r'' |----- | colspan="3" | <hr> |----- | align="right" | 1071 || align="right" | 1029 | align="right" | 42 |----- | align="right" | 1029 || align="right" | 42 | align="right" | 21 |----- | align="right" | 42 || align="right" | 21 | align="right" | 0 |----- | align="right" | 21 || align="right" | 0 |} === 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) de '''a''' par '''b''' | PGCD=PGCD(b, r) Finsi === Algorithme en langage C === <source lang='C'> int pgcd(int m, int n) { if (n == 0) { return m; } else { return pgcd(n, m%n); } } </source> Ou, de manière plus concise : <source lang='C'> int pgcd(int m, int n) { return n ? pgcd(n, m%n) : m; } </source> === Algorithme en langage PHP === <source lang='PHP'> function pgcd($a, $b) { for($c = $a % $b ; $c != 0 ; $c = $a % $b) { $a = $b; $b = $c; } return $b; } </source> Avec une fonction récursive, le code est plus simple : <source lang='PHP'> function pgcd($a, $b) { if($a % $b==0) return $b; else return pgcd($b, $a % $b); } </source> == Remarque historique == Au début, [[Euclide]] a formulé le problème de façon [[géométrie|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 <math>(a_n)</math> par division euclidienne montre que, pour tout <math>n</math> tel que <math>a_{n+1}</math> est non nul, il existe un entier <math>q_{n+2}</math> tel que : <math> a_{n}=q_{n+2}\times a_{n+1}+a_{n+2}</math> avec de plus <math>0\leq a_{n+2}<a_{n+1}</math>. La suite d'entiers naturels <math>(a_n)</math> est donc strictement décroissante, et donc vaut <math>0</math> à un certain rang. L'existence d'un dernier reste non nul est ainsi établie. Soit <math>N+1</math> l'indice de ce dernier reste non nul. Il faut montrer que <math>a_{N+1}</math> est bien le PGCD cherché. La relation précédente s'écrit donc ici <math>a_N=q_{N+2}\times a_{N+1}</math>, qui montre que <math>a_{N+1}</math> [[divisibilité|divise]] <math>a_N</math>. Ecrivant ensuite <math>a_{N-1}=q_{N+1}\times a_N+a_{N+1}</math>, on en déduit que <math>a_{N+1}</math> divise aussi <math>a_{N-1}</math> ; puis, de même, et par récurrence, que <math>a_{N+1}</math> divise tous les termes de la suite <math>a_n</math> ; en particulier les premiers termes <math>a</math> et <math>b</math>. <math>a_{N+1}</math> est donc bien un diviseur commun de <math>a</math> et <math>b</math>. Réciproquement, tout diviseur commun de ''a'' et ''b'' divisera aussi <math>a_2=a-q_2\times b</math>, et à nouveau par récurrence, divisera tous les termes de la suite <math>(a_n)</math> ; donc en particulier <math>a_{N+1}</math>. <math>a_{N+1}</math> 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é == {{...}} En étudiant l'exécution de l'algorithme d'Euclide, il apparaît que les nombres qui exigent le plus d'étapes sont les nombres consécutifs de la [[suite de Fibonacci]], et dans le pire des cas cela demande O(''n'') divisions, où ''n'' est le nombre de bits des nombres en entrée (voir la [[notations de Landau|notation grand O]]). == Algorithme étendu aux coefficients 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 : <math>au+bv=a_{N+1}=PGCD(a,b)</math>. L'algorithme d'Euclide convenablement adapté permet de calculer de tels coefficients. === Description === Pour cela, on introduit deux suites <math>(u_n)</math> et <math>(v_n)</math> telles que pour tout ''n'', on ait la relation : <math>au_n+bv_n=a_n</math>. Si de telles suites existent, les termes <math>u_{N+1},v_{N+1}</math> constitueront une paire de coefficients de Bezout pour ''a'' et ''b''. On peut choisir <math>u_0=1, v_0=0</math> puis <math>u_1=0,v_1=1</math>, puis la relation de récurrence de pas 2 entre les <math>a_n</math> montre : <math> 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}) </math> On peut ainsi définir <math>(u_n)</math> par la relation de récurrence de pas 2 : <math>u_{n+2}=u_n-q_{n+2}u_{n+1}</math> et l'initialisation précédente, et <math>(v_n)</math> par <math>v_{n+2}=v_n-q_{n+2}v_{n+1}</math> 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 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 == {{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 : :<math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}}</math>. 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 : * <math>\frac{1071}{1029} = \mathbf{1} = \frac{1}{1}</math> * <math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24}} = \frac{25}{24}</math> * <math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}} = \frac{1071}{1029}</math> Cette méthode peut également être utilisée pour des [[nombre réel|nombres réels]] ''a'' et '' b'' ;&nbsp; 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 [[nombre irrationnel|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 [[approximant de Padé|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 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 permet de très intéressants développements (voir par exemple la démonstration de l'irrationalité de ζ(3)). == Voir aussi == * [[Algorithme d'Euclide étendu]] * [[Lemme d'Euclide]] === Liens externes === * [http://ens.math.univ-montp2.fr/SPIP/-Anthypherese- Calcul graphique du PGCD avec Geoplan (Java)] * [http://laurent.petitprez.free.fr/calculator.php Calcul détaillé du pgcd de deux entiers] {{Portail mathématiques}} [[Catégorie:Théorie algorithmique des nombres|Euclide,Algorithme d']] [[Catégorie:Algorithme numérique|Euclide,Algorithme d']] [[ar:خوارزمية إقليدس]] [[bg:Алгоритъм на Евклид]] [[ca:Algorisme d'Euclides]] [[cs:Euklidův algoritmus]] [[de:Euklidischer Algorithmus]] [[el:Αλγόριθμος του Ευκλείδη]] [[en:Euclidean algorithm]] [[es:Algoritmo de Euclides]] [[fi:Eukleideen algoritmi]] [[hu:Euklidészi algoritmus]] [[id:Algoritma Euklidean]] [[it:Algoritmo di Euclide]] [[ja:ユークリッドの互除法]] [[ko:유클리드 호제법]] [[lt:Euklido algoritmas]] [[lv:Eiklīda algoritms]] [[nds:Euklidsch Algorithmus]] [[nl:Algoritme van Euclides]] [[no:Euklids algoritme]] [[pl:Algorytm Euklidesa]] [[pt:Algoritmo de Euclides]] [[ru:Алгоритм Евклида]] [[simple:Euclidean algorithm]] [[sl:Evklidov algoritem]] [[sr:Еуклидов алгоритам]] [[sv:Euklides algoritm]] [[tr:Öklid algoritması]] [[uk:Алгоритм Евкліда]] [[vi:Giải thuật Euclid]] [[zh:輾轉相除法]]