Algorithme d'Euclide

Infos
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. 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 car
Algorithme d'Euclide

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. 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 \mathbb 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 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 facteurs invariants.

Remarque préliminaire

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

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 (a_n)_n est définie par récurrence de pas 2, plus précisément par divisions euclidiennes successives ; la suite est initialisée par a_0=a, a_1=b, puis propagée par la règle de récurrence : tant que a_ est non nul, a_ est défini comme le reste de la division euclidienne de a_n par a_. 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 dernier reste non nul.

Exemple

right Calculons, par exemple, le pgcd de 1071 et 1029 (égal à 21) par cet algorithme avec les étapes suivantes :

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

int pgcd(int m, int n)

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 (a_n) par division euclidienne montre que, pour tout n tel que a_ est non nul, il existe un entier q_ tel que : a_=q_\times a_+a_ avec de plus 0\leq a_
Sujets connexes
Algorithme d'Euclide étendu   Algorithmique   Anneau (mathématiques)   Anneau euclidien   Approximant de Padé   Divisibilité   Division euclidienne   Décomposition en produit de facteurs premiers   Entier relatif   Euclide   Fraction continue   Géométrie   Identité de Bézout   Lemme d'Euclide   Nombre irrationnel   Nombre réel   Polynôme   Raisonnement par récurrence   Suite de Fibonacci   Série de Taylor   Théorème des facteurs invariants  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^