Algorithme euclidien - Euclidean algorithm

La méthode d'Euclide pour trouver le plus grand diviseur commun (GCD) de deux longueurs de départ BA et DC, toutes deux définies comme étant des multiples d'une longueur "unitaire" commune. La longueur DC étant plus courte, elle est utilisée pour "mesurer" BA, mais une seule fois car le reste EA est inférieur à DC. EA mesure maintenant (deux fois) la longueur plus courte DC, le reste FC étant plus court que EA. Ensuite, FC mesure (trois fois) la longueur EA. Puisqu'il n'y a pas de reste, le processus se termine par FC étant le GCD. À droite , l'exemple de Nicomaque avec les nombres 49 et 21 résultant en leur PGCD de 7 (dérivé de Heath 1908:300).

En mathématiques , l' algorithme d' Euclide , ou algorithme d'Euclide , est une méthode efficace pour calculer le plus grand diviseur commun (GCD) de deux entiers (nombres), le plus grand nombre qui les divise tous les deux sans reste . Il tire son nom du mathématicien grec Euclide , qui l'a décrit pour la première fois dans ses Éléments (vers 300 av. J.-C.). C'est un exemple d' algorithme , une procédure pas à pas pour effectuer un calcul selon des règles bien définies, et c'est l'un des algorithmes les plus anciens d'usage courant. Il peut être utilisé pour réduire les fractions à leur forme la plus simple et fait partie de nombreux autres calculs de théorie des nombres et de cryptographie.

L'algorithme d'Euclide repose sur le principe que le plus grand diviseur commun de deux nombres ne change pas si le plus grand nombre est remplacé par sa différence avec le plus petit nombre. Par exemple, 21 est le PGCD de 252 et 105 (comme 252 = 21 × 12 et 105 = 21 × 5), et le même nombre 21 est également le PGCD de 105 et 252 − 105 = 147. Étant donné que ce remplacement réduit le plus grand des deux nombres, la répétition de ce processus donne des paires de nombres successivement plus petites jusqu'à ce que les deux nombres deviennent égaux. Lorsque cela se produit, ils sont le PGCD des deux nombres d'origine. En inversant les étapes ou en utilisant l' algorithme d'Euclide étendu , le PGCD peut être exprimé comme une combinaison linéaire des deux nombres originaux, c'est-à-dire la somme des deux nombres, chacun multiplié par un entier (par exemple, 21 = 5 × 105 + (−2) × 252). Le fait que le GCD puisse toujours s'exprimer de cette manière est connu comme l'identité de Bézout .

La version de l'algorithme euclidien décrite ci-dessus (et par Euclid) peut prendre de nombreuses étapes de soustraction pour trouver le PGCD lorsque l'un des nombres donnés est beaucoup plus grand que l'autre. Une version plus efficace de l'algorithme raccourcit ces étapes, remplaçant plutôt le plus grand des deux nombres par son reste lorsqu'il est divisé par le plus petit des deux (avec cette version, l'algorithme s'arrête lorsqu'il atteint un reste nul). Avec cette amélioration, l'algorithme ne nécessite jamais plus d'étapes que cinq fois le nombre de chiffres (base 10) du plus petit entier. Cela a été prouvé par Gabriel Lamé en 1844, et marque le début de la théorie de la complexité computationnelle . Des méthodes supplémentaires pour améliorer l'efficacité de l'algorithme ont été développées au 20ème siècle.

L'algorithme d'Euclide a de nombreuses applications théoriques et pratiques. Il est utilisé pour réduire les fractions à leur forme la plus simple et pour effectuer des divisions en arithmétique modulaire . Les calculs utilisant cet algorithme font partie des protocoles cryptographiques utilisés pour sécuriser les communications Internet et des méthodes permettant de casser ces cryptosystèmes en factorisant de grands nombres composites . L'algorithme euclidien peut être utilisé pour résoudre des équations diophantiennes , telles que la recherche de nombres qui satisfont à plusieurs congruences selon le théorème des restes chinois , pour construire des fractions continues et pour trouver des approximations rationnelles précises des nombres réels. Enfin, il peut être utilisé comme outil de base pour prouver des théorèmes en théorie des nombres tels que le théorème des quatre carrés de Lagrange et l' unicité des factorisations premières . L'algorithme d'origine n'était décrit que pour les nombres naturels et les longueurs géométriques (nombres réels), mais l'algorithme a été généralisé au XIXe siècle à d'autres types de nombres, tels que les entiers gaussiens et les polynômes d'une variable. Cela a conduit à des notions algébriques abstraites modernes telles que les domaines euclidiens .

Contexte : plus grand diviseur commun

L'algorithme d'Euclide calcule le plus grand diviseur commun (GCD) de deux nombres naturels a et b . Le plus grand diviseur commun g est le plus grand nombre naturel qui divise à la fois a et b sans laisser de reste. Les synonymes du GCD incluent le plus grand facteur commun (GCF), le plus grand facteur commun (HCF), le plus grand diviseur commun (HCD) et la plus grande mesure commune (GCM). Le plus grand diviseur commun est souvent écrit comme pgcd( ab ) ou, plus simplement, comme ( ab ), bien que cette dernière notation soit ambiguë, également utilisée pour des concepts tels qu'un idéal dans l' anneau des entiers , qui est étroitement liés à GCD.

Si PGCD ( ab ) = 1, a et b sont dits être coprime (ou relativement premier). Cette propriété n'implique pas que a ou b soient eux-mêmes des nombres premiers . Par exemple, ni 6 ni 35 n'est un nombre premier, puisqu'ils ont tous deux deux facteurs premiers : 6 = 2 × 3 et 35 = 5 × 7. Néanmoins, 6 et 35 sont premiers entre eux. Aucun nombre naturel autre que 1 ne divise à la fois 6 et 35, car ils n'ont pas de facteurs premiers en commun.

"Grand rectangle mince divisé en une grille de carrés. Le rectangle mesure deux carrés de large et cinq carrés de haut."
Un rectangle de 24 par 60 est recouverte d' une dizaine de 12 par 12 carreaux carrés, où 12 est le PGCD de 24 et 60. Plus généralement, un un -by- b rectangle peut être recouverte de carreaux carrés de côté de longueur c seulement si c est un diviseur commun de a et b .

Soit g = pgcd( ab ). Puisque a et b sont tous deux des multiples de g , ils peuvent s'écrire a  =  mg et b  =  ng , et il n'y a pas de plus grand nombre G  >  g pour lequel cela est vrai. Les nombres naturels m et n doivent être premiers entre eux, car tout facteur commun pourrait être factorisé à partir de m et n pour augmenter g . Ainsi, tout autre nombre c qui divise à la fois a et b doit également diviser g . Le plus grand commun diviseur g de a et b est l'unique diviseur commun (positif) de a et b qui est divisible par tout autre commun diviseur c .

Le GCD peut être visualisé comme suit. Considérons une aire rectangulaire a par b , et tout diviseur commun c qui divise à la fois a et b exactement. Les côtés du rectangle peuvent être divisés en segments de longueur c , ce qui divise le rectangle en une grille de carrés de longueur de côté c . Le plus grand commun diviseur g est la plus grande valeur de c pour laquelle cela est possible. À titre d'illustration, une zone rectangulaire de 24 x 60 peut être divisée en une grille de : carrés 1 x 1, carrés 2 x 2, carrés 3 x 3, carrés 4 x 4, carrés 6 x -6 carrés ou 12 par 12 carrés. Par conséquent, 12 est le plus grand diviseur commun de 24 et 60. Une zone rectangulaire de 24 par 60 peut être divisée en une grille de 12 par 12 carrés, avec deux carrés le long d'un bord (24/12 = 2) et cinq carrés le long de l'autre (60/12 = 5).

Le PGCD de deux nombres a et b est le produit des facteurs premiers partagés par les deux nombres, où un même facteur premier peut être utilisé plusieurs fois, mais seulement tant que le produit de ces facteurs divise à la fois a et b . Par exemple, puisque 1386 peut être factorisé en 2 × 3 × 3 × 7 × 11, et 3213 peut être factorisé en 3 × 3 × 3 × 7 × 17, le plus grand diviseur commun de 1386 et 3213 est égal à 63 = 3 × 3 × 7, le produit de leurs facteurs premiers communs. Si deux nombres n'ont pas de facteurs premiers en commun, leur plus grand commun diviseur est 1 (obtenu ici comme instance du produit vide ), c'est-à-dire qu'ils sont premiers entre eux. Un avantage clé de l'algorithme euclidien est qu'il peut trouver le PGCD efficacement sans avoir à calculer les facteurs premiers. La factorisation de grands nombres entiers est considérée comme un problème de calcul très difficile, et la sécurité de nombreux protocoles cryptographiques largement utilisés est basée sur son infaisabilité.

Une autre définition du GCD est utile en mathématiques avancées, en particulier en théorie des anneaux . Le plus grand commun diviseur g   de deux nombres non nuls a et b est aussi leur plus petite combinaison linéaire intégrale positive, c'est-à-dire le plus petit nombre positif de la forme ua  +  vbu et v sont des entiers. L'ensemble de toutes les combinaisons linéaires intégrales de a et b est en fait le même que l'ensemble de tous les multiples de g ( mg , où m est un entier). En langage mathématique moderne, l' idéal généré par a et b est l'idéal généré par  g seul (un idéal généré par un seul élément est appelé idéal principal et tous les idéaux des entiers sont des idéaux principaux). Certaines propriétés du PGCD sont en fait plus faciles à voir avec cette description, par exemple le fait que tout diviseur commun de a et b divise également le PGCD (il divise les deux termes de ua  +  vb ). L'équivalence de cette définition GCD avec les autres définitions est décrite ci-dessous.

Le PGCD de trois nombres ou plus est égal au produit des facteurs premiers communs à tous les nombres, mais il peut également être calculé en prenant à plusieurs reprises les PGCD de paires de nombres. Par exemple,

pgcd( abc ) = pgcd( a , pgcd( bc )) = pgcd(pgcd( ab ),  c ) = pgcd(pgcd( ac ),  b ).

Ainsi, l'algorithme d'Euclide, qui calcule le PGCD de deux entiers, suffit pour calculer le PGCD d'un nombre arbitraire d'entiers.

La description

Procédure

L'algorithme d'Euclide procède en une série d'étapes telles que la sortie de chaque étape est utilisée comme entrée pour la suivante. Soit k un entier qui compte les pas de l'algorithme, en commençant par zéro. Ainsi, l'étape initiale correspond à k  = 0, l'étape suivante correspond à k  = 1, et ainsi de suite.

Chaque étape commence par deux restes non négatifs r k -1 et r k -2 . Puisque l'algorithme garantit que les restes diminuent régulièrement à chaque pas, r k -1 est inférieur à son prédécesseur r k -2 . Le but du k ème étape consiste à trouver un quotient q k et reste r k qui satisfont l'équation

et qui ont 0 r k  <  r k −1 . En d'autres termes, des multiples du plus petit nombre r k -1 sont soustraits du plus grand nombre r k -2 jusqu'à ce que le reste r k soit inférieur à r k -1 .

A l'étape initiale ( k  = 0), les restes r -2 et r -1 sont égaux à a et b , les nombres pour lesquels le PGCD est recherché. A l'étape suivante ( k  = 1), les restes sont égaux à b et le reste r 0 de l'étape initiale, et ainsi de suite. Ainsi, l'algorithme peut être écrit comme une séquence d'équations

Si a est plus petit que b , la première étape de l'algorithme échange les nombres. Par exemple, si a  <  b , le quotient initial q 0 est égal à zéro et le reste r 0 est a . Ainsi, r k est plus petit que son prédécesseur r k −1 pour tout k  0.

Étant donné que les restes diminuent à chaque pas mais ne peuvent jamais être négatifs, un reste r N doit éventuellement être égal à zéro, moment auquel l'algorithme s'arrête. Le reste final non nul r N -1 est le plus grand commun diviseur de a et b . Le nombre N ne peut pas être infini car il n'y a qu'un nombre fini d'entiers non négatifs entre le reste initial r 0 et zéro.

Preuve de validité

La validité de l'algorithme d'Euclide peut être prouvée par un argument en deux étapes. Dans la première étape, le reste final non nul r N -1 est montré pour diviser à la fois a et b . Puisqu'il s'agit d'un commun diviseur, il doit être inférieur ou égal au plus grand commun diviseur g . Dans la deuxième étape, on montre que tout diviseur commun de a et b , y compris g , doit diviser r N -1 ; par conséquent, g doit être inférieur ou égal à r N -1 . Ces deux conclusions sont incohérentes à moins que r N −1  =  g .

Pour démontrer que r N −1 divise à la fois a et b (la première étape), r N −1 divise son prédécesseur r N −2

r N -2 = q N r N -1

puisque le reste final r N est nul. r N −1 divise également son prochain prédécesseur r N −3

r N -3 = q N -1 r N -2 + r N -1

car il divise les deux termes du côté droit de l'équation. En itérant le même argument, r N -1 divise tous les restes précédents, y compris a et b . Aucun des restes précédents r N -2 , r N -3 , etc. ne divise a et b , puisqu'ils laissent un reste. Etant donné que r N -1 est un diviseur commun de a et b , r N -1  ≤  g .

Dans la seconde étape, un nombre quelconque naturel c qui divise la fois un et b (en d' autres termes, tout commun diviseur de a et b ) divise les restes r k . Par définition, a et b peuvent être écrits comme des multiples de c  : a  =  mc et b  =  nc , où m et n sont des nombres naturels. Par conséquent, c divise le reste initial r 0 , puisque r 0  =  a  −  q 0 b  =  mc  −  q 0 nc  = ( m  −  q 0 n ) c . Un raisonnement analogue montre que c divise aussi les restes suivants r 1 , r 2 , etc. Par conséquent, le plus grand commun diviseur g fracture doit r N -1 , ce qui implique que g  ≤  r N -1 . Puisque la première partie de l'argument montrait l'inverse ( r N −1  ≤  g ), il s'ensuit que g  =  r N −1 . Ainsi, g est le plus grand diviseur commun de toutes les paires suivantes :

g = pgcd( a , b ) = pgcd( b , r 0 ) = pgcd( r 0 , r 1 ) = … = pgcd( r N −2 , r N −1 ) = r N −1 .

Exemple travaillé

Animation dans laquelle des tuiles carrées de plus en plus petites sont ajoutées pour couvrir complètement un rectangle.
Animation basée sur la soustraction de l'algorithme d'Euclide. Le rectangle initial a des dimensions a  = 1071 et b  = 462. Des carrés de taille 462×462 y sont placés en laissant un rectangle de 462×147. Ce rectangle est carrelé avec des carrés de 147 × 147 jusqu'à ce qu'il reste un rectangle de 21 × 147, qui à son tour est carrelé avec des carrés de 21 × 21, ne laissant aucune zone découverte. Le plus petit carré, 21, est le PGCD de 1071 et 462.

À titre d'illustration, l'algorithme d'Euclide peut être utilisé pour trouver le plus grand diviseur commun de a  = 1071 et b  = 462. Pour commencer, les multiples de 462 sont soustraits de 1071 jusqu'à ce que le reste soit inférieur à 462. Deux de ces multiples peuvent être soustraits ( q 0  = 2), laissant un reste de 147 :

1071 = 2 × 462 + 147.

Ensuite, des multiples de 147 sont soustraits de 462 jusqu'à ce que le reste soit inférieur à 147. Trois multiples peuvent être soustraits ( q 1  = 3), laissant un reste de 21 :

462 = 3 × 147 + 21.

Ensuite, les multiples de 21 sont soustraits de 147 jusqu'à ce que le reste soit inférieur à 21. Sept multiples peuvent être soustraits ( q 2  = 7), ne laissant aucun reste :

147 = 7 × 21 + 0.

Puisque le dernier reste est zéro, l'algorithme se termine par 21 comme plus grand diviseur commun de 1071 et 462. Ceci est en accord avec le pgcd (1071, 462) trouvé par la factorisation en nombres premiers ci-dessus . Sous forme de tableau, les étapes sont :

Étape k Équation Quotient et reste
0 1071 = q 0 462 + r 0 q 0 = 2 et r 0 = 147
1 462 = q 1 147 + r 1 q 1 = 3 et r 1 = 21
2 147 = q 2 21 + r 2 q 2 = 7 et r 2 = 0 ; l'algorithme se termine

Visualisation

L'algorithme euclidien peut être visualisé en termes d'analogie de pavage donnée ci-dessus pour le plus grand diviseur commun. Supposons que nous souhaitions couvrir exactement un rectangle a par b avec des carreaux carrés, où a est le plus grand des deux nombres. Nous essayons d'abord de carreler le rectangle en utilisant des carreaux carrés b par b ; cependant, cela laisse un rectangle résiduel r 0 -by- b jusqu'à ce que r 0  <  b . Nous essayons ensuite de carreler le rectangle résiduel avec r 0 -par- r 0 carreaux carrés. Cela laisse un deuxième rectangle résiduel r 1 -by- r 0 , que nous essayons de carreler en utilisant r 1 -by- r 1 carreaux carrés, et ainsi de suite. La séquence se termine lorsqu'il n'y a pas de rectangle résiduel, c'est-à-dire lorsque les carreaux carrés couvrent exactement le rectangle résiduel précédent. La longueur des côtés de la plus petite tuile carrée est le PGCD des dimensions du rectangle d'origine. Par exemple, la plus petite tuile carrée de la figure adjacente est 21 par 21 (affichée en rouge) et 21 est le PGCD de 1071 et 462, les dimensions du rectangle d'origine (affichée en vert).

Division euclidienne

A chaque étape k , l'algorithme d' Euclide calcule un quotient q k et reste r k à partir de deux nombres r k -1 et r k -2

r k -2 = q k r k -1 + r k

r k est non négatif et strictement inférieur à la valeur absolue de r k -1 . Le théorème qui sous-tend la définition de la division euclidienne assure qu'un tel quotient et ce reste existent toujours et sont uniques.

Dans la version originale de l'algorithme d'Euclide, le quotient et le reste sont trouvés par soustraction répétée ; c'est-à-dire que r k -1 est soustrait de r k -2 à plusieurs reprises jusqu'à ce que le reste r k soit inférieur à r k -1 . Après cela , r k et r k -1 sont échangés et le processus est répété. La division euclidienne réduit toutes les étapes entre deux échanges en une seule étape, donc plus efficace. De plus, les quotients ne sont pas nécessaires, on peut donc remplacer la division euclidienne par l' opération modulo , qui ne donne que le reste. Ainsi, l'itération de l'algorithme d'Euclide devient simplement

r k = r k -2 mod r k -1 .

Implémentations

Les implémentations de l'algorithme peuvent être exprimées en pseudocode . Par exemple, la version basée sur la division peut être programmée comme

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

Au début de la k ième itération, la variable b contient le dernier reste r k −1 , tandis que la variable a contient son prédécesseur, r k −2 . L'étape b  : = a mod b est équivalente à la formule de récurrence ci - dessus r kr k -2 mod r k -1 . La variable temporaire t contient la valeur de r k -1 tandis que l'autre reste r k est calculé. A la fin de l'itération de boucle, la variable b contient le reste r k , alors que la variable a tient son prédécesseur, r k -1 .

(Si les entrées négatives sont autorisées, ou si la fonction mod peut renvoyer des valeurs négatives, la dernière ligne doit être changée en return max (a, -a).)

Dans la version basée sur la soustraction, qui était la version originale d'Euclide, le calcul du reste ( ) est remplacé par une soustraction répétée. Contrairement à la version basée sur la division, qui fonctionne avec des entiers arbitraires en entrée, la version basée sur la soustraction suppose que l'entrée est constituée d'entiers positifs et s'arrête lorsque a = b : b := a mod b

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Les variables a et b contiennent alternativement les restes précédents r k -1 et r k -2 . Supposons que a soit plus grand que b au début d'une itération ; alors a vaut r k −2 , puisque r k −2 > r k −1 . Au cours de l'itération de la boucle, a est réduit par des multiples du reste précédent b jusqu'à ce que a soit inférieur à b . Alors a est le reste suivant r k . Ensuite, b est réduit par des multiples de a jusqu'à ce qu'il soit à nouveau plus petit que a , donnant le reste suivant r k +1 , et ainsi de suite.

La version récursive est basée sur l'égalité des PGCD des restes successifs et la condition d'arrêt gcd( r N −1 , 0) =  r N −1 .

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(Comme ci-dessus, si les entrées négatives sont autorisées, ou si la fonction mod peut retourner des valeurs négatives, l'instruction " return a" doit être changée en " return max (a, -a)".)

A titre d'illustration, le pgcd (1071, 462) est calculé à partir du pgcd équivalent (462, 1071 mod 462) = pgcd (462, 147). Ce dernier GCD est calculé à partir du pgcd(147, 462 mod 147) = pgcd(147, 21), qui à son tour est calculé à partir du pgcd(21, 147 mod 21) = pgcd(21, 0) = 21.

Méthode des moindres restes absolus

Dans une autre version de l'algorithme d'Euclide, le quotient à chaque étape est augmenté de un si le reste négatif résultant est plus petit que le reste positif typique. Auparavant, l'équation

r k -2 = q k r k -1 + r k

supposé que | r k −1 | >  R k  > 0 . Cependant, un autre reste négatif e k peut être calculé :

r k -2 = ( q k + 1) r k -1 + e k

si r k −1  > 0 ou

r k −2 = ( q k − 1) r k −1 + e k

si r k -1  < 0 .

Si r k est remplacé par e k . quand | e k | < | r k | , alors on obtient une variante de l'algorithme euclidien telle que

| r k | | r k −1 | / 2

à chaque étape.

Leopold Kronecker a montré que cette version nécessite le moins d'étapes de toutes les versions de l'algorithme d'Euclide. Plus généralement, il a été prouvé que, pour chaque nombre d'entrée a et b , le nombre de pas est minimal si et seulement si q k est choisi dans l'ordre où est le nombre d' or .

Développement historique

"Représentation d'Euclide en homme barbu tenant une paire de séparateurs sur une tablette."
L'algorithme d'Euclide a probablement été inventé avant Euclide , représenté ici tenant une boussole dans un tableau d'environ 1474.

L'algorithme d'Euclide est l'un des algorithmes les plus anciens d'usage courant. Il apparaît dans les Éléments d'Euclide (vers 300 av. J.-C.), en particulier dans le Livre 7 (Propositions 1–2) et le Livre 10 (Propositions 2–3). Dans le livre 7, l'algorithme est formulé pour des nombres entiers, alors que dans le livre 10, il est formulé pour des longueurs de segments de ligne. (Dans l'usage moderne, on dirait qu'il a été formulé là pour des nombres réels . Mais les longueurs, les aires et les volumes, représentés comme des nombres réels dans l'usage moderne, ne sont pas mesurés dans les mêmes unités et il n'y a pas d'unité naturelle de longueur, aire, ou volume; le concept de nombres réels était inconnu à l'époque.) Ce dernier algorithme est géométrique. Le PGCD de deux longueurs a et b correspond à la plus grande longueur g que les mesures a et b de façon uniforme; en d'autres termes, les longueurs a et b sont toutes deux des multiples entiers de la longueur g .

L'algorithme n'a probablement pas été découvert par Euclide , qui a compilé les résultats des premiers mathématiciens dans ses Éléments . Le mathématicien et historien BL van der Waerden suggère que le livre VII dérive d'un manuel sur la théorie des nombres écrit par des mathématiciens de l'école de Pythagore . L'algorithme était probablement connu par Eudoxe de Cnide (environ 375 avant JC). L'algorithme peut même être antérieur à Eudoxe, à en juger par l'utilisation du terme technique ( anthyphairesis , soustraction réciproque) dans les travaux d'Euclide et d' Aristote .

Des siècles plus tard, l'algorithme d'Euclide a été découvert indépendamment à la fois en Inde et en Chine, principalement pour résoudre les équations diophantiennes apparues en astronomie et créer des calendriers précis. À la fin du Ve siècle, le mathématicien et astronome indien Aryabhata a décrit l'algorithme comme le « pulvérisateur », peut-être en raison de son efficacité à résoudre les équations diophantiennes. Bien qu'un cas particulier du théorème du reste chinois ait déjà été décrit dans le livre chinois Sunzi Suanjing , la solution générale a été publiée par Qin Jiushao dans son livre de 1247 Shushu Jiuzhang (數書九章Traité mathématique en neuf sections ). L'algorithme d' Euclide a d' abord été décrit numériquement et popularisé en Europe dans la deuxième édition de de Bachet Problèmes plaisants et Delectables ( agréable et problèmes agréables , 1624). En Europe, il a également été utilisé pour résoudre des équations diophantiennes et pour développer des fractions continues . L' algorithme euclidien étendu a été publié par le mathématicien anglais Nicholas Saunderson , qui l'a attribué à Roger Cotes comme méthode de calcul efficace des fractions continues.

Au 19ème siècle, l'algorithme euclidien a conduit au développement de nouveaux systèmes de nombres, tels que les entiers gaussiens et les entiers d'Eisenstein . En 1815, Carl Gauss a utilisé l'algorithme euclidien pour démontrer la factorisation unique des entiers gaussiens , bien que son travail ait été publié pour la première fois en 1832. Gauss a mentionné l'algorithme dans ses Disquisitiones Arithmeticae (publié en 1801), mais uniquement comme méthode pour les fractions continues . Peter Gustav Lejeune Dirichlet semble avoir été le premier à décrire l'algorithme euclidien comme la base d'une grande partie de la théorie des nombres. Lejeune Dirichlet a noté que de nombreux résultats de la théorie des nombres, tels que la factorisation unique, seraient vrais pour tout autre système de nombres auquel l'algorithme d'Euclide pourrait être appliqué. Les cours de Lejeune Dirichlet sur la théorie des nombres ont été édités et étendus par Richard Dedekind , qui a utilisé l'algorithme d'Euclide pour étudier les entiers algébriques , un nouveau type général de nombre. Par exemple, Dedekind a été le premier à prouver le théorème des deux carrés de Fermat en utilisant la factorisation unique des entiers gaussiens. Dedekind a également défini le concept d'un domaine euclidien , un système numérique dans lequel une version généralisée de l'algorithme euclidien peut être définie (comme décrit ci - dessous ). Au cours des dernières décennies du XIXe siècle, l'algorithme euclidien est progressivement éclipsé par la théorie plus générale des idéaux de Dedekind .

"[L'algorithme euclidien] est le grand-père de tous les algorithmes, car c'est le plus ancien algorithme non trivial qui a survécu jusqu'à nos jours."

Donald Knuth , L'art de la programmation informatique, vol. 2 : Algorithmes seminumériques , 2e édition (1981), p. 318.

D'autres applications de l'algorithme d'Euclide ont été développées au 19ème siècle. En 1829, Charles Sturm a montré que l'algorithme était utile dans la méthode de la chaîne de Sturm pour compter les racines réelles des polynômes dans un intervalle donné.

L'algorithme d'Euclide a été le premier algorithme de relation entière , qui est une méthode pour trouver des relations entières entre des nombres réels proportionnels. Plusieurs nouveaux algorithmes de relation entière ont été développés, tels que l'algorithme de Helaman Ferguson et RW Forcade (1979) et l' algorithme LLL .

En 1969, Cole et Davie ont développé un jeu à deux joueurs basé sur l'algorithme d'Euclide, appelé The Game of Euclid , qui a une stratégie optimale. Les joueurs commencent par deux piles de a et b pierres. Les joueurs retirent à tour de rôle m multiples de la plus petite pile de la plus grande. Ainsi, si les deux piles sont constituées de x et y pierres, où x est plus grand que y , le joueur suivant peut réduire la plus grande pile de x pierres à xmes pierres, tant que ce dernier est un entier non négatif. Le gagnant est le premier joueur à réduire une pile à zéro pierre.

Applications mathématiques

L'identité de Bézout

L'identité de Bézout stipule que le plus grand diviseur commun g de deux nombres entiers a et b peut être représenté comme une somme linéaire des deux nombres originaux a et b . En d'autres termes, il est toujours possible de trouver des entiers s et t tels que g  =  sa  +  tb .

Les entiers s et t peuvent être calculés à partir des quotients q 0 , q 1 , etc. en inversant l'ordre des équations dans l'algorithme d'Euclide. En commençant par l'avant-dernière équation, g peut être exprimé en fonction du quotient q N −1 et des deux restes précédents, r N −2 et r N −3 :

g = r N −1 = r N −3q N −1 r N −2  .

Ces deux restes peuvent également être exprimés en fonction de leurs quotients et restes précédents,

r N −2 = r N −4q N −2 r N −3 et
r N -3 = r N -5 - q N -3 r N -4  .

La substitution de ces formules pour r N -2 et r N -3 dans la première équation donne g comme somme linéaire des restes r N -4 et r N -5 . Le processus de substitution des restes par des formules impliquant leurs prédécesseurs peut être poursuivi jusqu'à ce que les nombres originaux a et b soient atteints :

r 2 = r 0q 2 r 1
r 1 = bq 1 r 0
r 0 = aq 0 b .

Après que tous les restes r 0 , r 1 , etc. aient été substitués, l'équation finale exprime g comme une somme linéaire de a et b : g  =  sa  +  tb . L'identité de Bézout , et donc l'algorithme précédent, peuvent tous deux être généralisés au contexte des domaines euclidiens .

Principaux idéaux et problèmes connexes

L'identité de Bézout fournit encore une autre définition du plus grand commun diviseur g de deux nombres a et b . Considérons l'ensemble de tous les nombres ua  +  vb , où u et v sont deux nombres entiers quelconques. Puisque a et b sont tous deux divisibles par g , chaque nombre de l'ensemble est divisible par g . En d'autres termes, chaque nombre de l'ensemble est un multiple entier de g . Ceci est vrai pour tout diviseur commun de a et b . Cependant, contrairement à d'autres diviseurs communs, le plus grand diviseur commun est un membre de l'ensemble ; par l'identité de Bézout, choisir u  =  s et v  =  t donne g . Un diviseur commun plus petit ne peut pas être membre de l'ensemble, puisque chaque membre de l'ensemble doit être divisible par g . Inversement, tout multiple m de g peut être obtenu en choisissant u  =  ms et v  =  mt , où s et t sont les entiers de l'identité de Bézout. Cela peut être vu en multipliant l'identité de Bézout par m ,

mg = msa + vtt .

Par conséquent, l'ensemble de tous les nombres ua  +  vb est équivalent à l'ensemble des multiples m de g . En d'autres termes, l'ensemble de toutes les sommes possibles des multiples entiers de deux nombres ( a et b ) est équivalent à l'ensemble des multiples de pgcd( a , b ). On dit que le PGCD est le générateur de l' idéal de a et b . Cette définition GCD a conduit aux concepts algébriques abstraits modernes d'un idéal principal (un idéal généré par un seul élément) et d'un domaine idéal principal (un domaine dans lequel chaque idéal est un idéal principal).

Certains problèmes peuvent être résolus en utilisant ce résultat. Par exemple, considérons deux tasses à mesurer de volume a et b . En ajoutant/soustrayant u multiples de la première tasse et v multiples de la deuxième tasse, tout volume ua  +  vb peut être mesuré. Ces volumes sont tous des multiples de g  = pgcd( ab ).

Algorithme euclidien étendu

Les entiers s et t de l'identité de Bézout peuvent être calculés efficacement en utilisant l' algorithme d'Euclide étendu . Cette extension ajoute deux équations récursives à l'algorithme d'Euclide

s k = s k −2q k s k −1
t k = t k −2q k t k −1

avec les valeurs de départ

s -2 = 1, t -2 = 0
s -1 = 0, t -1 = 1.

En utilisant cette récursivité, les entiers de Bézout s et t sont donnés par s  =  s N et t  =  t N , où N+1 est le pas sur lequel l'algorithme se termine avec r N+1  = 0.

La validité de cette approche peut être démontrée par induction. Supposons que la formule de récursivité soit correcte jusqu'à l'étape k  − 1 de l'algorithme ; en d'autres termes, supposons que

r j = s j a + t j b

pour tout j inférieur à k . La k ème étape de l'algorithme donne l'équation

r k = r k −2q k r k −1 .

Puisque la formule de récursivité a été supposée correcte pour r k −2 et r k −1 , elles peuvent être exprimées en fonction des variables s et t correspondantes

r k = ( s k -2 a + t k -2 b ) - q k ( s k -1 a + t k -1 b ).

La réorganisation de cette équation donne la formule de récursivité pour l'étape k , comme requis

r k = s k a + t k b = ( s k −2q k s k −1 ) a + ( t k −2q k t k −1 ) b .

Méthode matricielle

Les entiers s et t peuvent également être trouvés en utilisant une méthode matricielle équivalente . La suite d'équations de l'algorithme d'Euclide

peut être écrit comme un produit de matrices de quotient 2 par 2 multipliant un vecteur de reste à deux dimensions

Soit M le produit de toutes les matrices quotients

Cela simplifie l'algorithme d'Euclide sous la forme

Pour exprimer g comme une somme linéaire de a et b , les deux membres de cette équation peuvent être multipliés par l' inverse de la matrice M . Le déterminant de M est égal à (−1) N +1 , puisqu'il est égal au produit des déterminants des matrices de quotient, dont chacun est moins un. Puisque le déterminant de M n'est jamais nul, le vecteur des restes finaux peut être résolu en utilisant l'inverse de M

Puisque l'équation du haut donne

g = (−1) N +1 ( m 22 am 12 b ),

les deux entiers de l'identité de Bézout sont s  = (−1) N +1 m 22 et t  = (−1) N m 12 . La méthode matricielle est aussi efficace que la récursivité équivalente, avec deux multiplications et deux additions par étape de l'algorithme d'Euclide.

Lemme d'Euclide et factorisation unique

L'identité de Bézout est essentielle à de nombreuses applications de l'algorithme d'Euclide, comme la démonstration de la factorisation unique des nombres en facteurs premiers. Pour illustrer cela, supposons qu'un nombre L puisse être écrit comme un produit de deux facteurs u et v , c'est-à-dire L  =  uv . Si un autre nombre w divise également L mais est premier avec u , alors w doit diviser v , par l'argument suivant : Si le plus grand diviseur commun de u et w est 1, alors les entiers s et t peuvent être trouvés tels que

1 = su + tw  .

par l'identité de Bézout. En multipliant les deux côtés par v, on obtient la relation

v = suv + twv = sL + twv  .

Puisque w divise les deux termes du membre de droite, il doit également diviser le membre de gauche, v . Ce résultat est connu sous le nom de lemme d'Euclide . Plus précisément, si un nombre premier divise L , alors il doit diviser au moins un facteur de L . Inversement, si un nombre w est premier à chacun d'une série de nombres a 1 , a 2 , ..., a n , alors w est également premier à leur produit, a 1  ×  a 2  × ... ×  a n .

Le lemme d'Euclide suffit à prouver que chaque nombre a une unique factorisation en nombres premiers. Pour le voir, supposons au contraire qu'il existe deux factorisations indépendantes de L en m et n facteurs premiers, respectivement

L = p 1 p 2p m = q 1 q 2q n  .

Puisque chaque nombre premier p divise L par hypothèse, il doit également diviser l'un des q facteurs ; puisque chaque q est également premier, il faut que p  =  q . La division itérative par les facteurs p montre que chaque p a une contrepartie égale q ; les deux factorisations premières sont identiques à l'exception de leur ordre. La factorisation unique des nombres en nombres premiers a de nombreuses applications dans les preuves mathématiques, comme indiqué ci-dessous.

Équations diophantiennes linéaires

"Une ligne diagonale allant du coin supérieur gauche au coin inférieur droit. Quinze cercles sont espacés à intervalles réguliers le long de la ligne. Les axes de coordonnées xy perpendiculaires ont leur origine dans le coin inférieur gauche ; la ligne croise l'axe des y en haut à gauche et croisez l'axe des x en bas à droite."
Tracé d'une équation diophantienne linéaire , 9 x  + 12 y  = 483. Les solutions sont représentées par des cercles bleus.

Les équations diophantiennes sont des équations dont les solutions sont restreintes à des nombres entiers ; ils portent le nom du mathématicien alexandrin du IIIe siècle Diophante . Une équation diophantienne linéaire typique cherche des entiers x et y tels que

hache + par = c

a , b et c sont des nombres entiers. Cela peut être écrit comme une équation pour x en arithmétique modulaire :

axc mod b .

Soit g le plus grand commun diviseur de a et b . Les deux termes de ax  +  by sont divisibles par g ; par conséquent, c doit également être divisible par g , ou l'équation n'a pas de solution. En divisant les deux côtés par c / g , l'équation peut être réduite à l'identité de Bezout

sa + tb = g

s et t peuvent être trouvés par l' algorithme d'Euclide étendu . Cela fournit une solution à l'équation diophantienne, x 1  =  s ( c / g ) et y 1  =  t ( c / g ).

En général, une équation diophantienne linéaire n'a pas de solutions, ou un nombre infini de solutions. Pour trouver ce dernier, considérons deux solutions, ( x 1y 1 ) et ( x 2y 2 ), où

hache 1 + par 1 = c = hache 2 + par 2

ou équivalent

a ( x 1x 2 ) = b ( y 2y 1 ).

Par conséquent, la plus petite différence entre deux solutions x est b / g , alors que la plus petite différence entre deux solutions y est a / g . Ainsi, les solutions peuvent être exprimées sous la forme

x = x 1bu / g
y = y 1 + au / g .

En permettant à u de varier sur tous les entiers possibles, une famille infinie de solutions peut être générée à partir d'une seule solution ( x 1y 1 ). Si les solutions doivent être des nombres entiers positifs ( x  > 0,  y  > 0), seul un nombre fini de solutions peut être possible. Cette restriction sur les solutions acceptables permet à certains systèmes d'équations diophantiennes avec plus d'inconnues que d'équations d'avoir un nombre fini de solutions ; ceci est impossible pour un système d'équations linéaires lorsque les solutions peuvent être n'importe quel nombre réel (voir Système sous-déterminé ).

Les inverses multiplicatifs et l'algorithme RSA

Un corps fini est un ensemble de nombres avec quatre opérations généralisées. Les opérations sont appelées addition, soustraction, multiplication et division et ont leurs propriétés habituelles, telles que la commutativité , l' associativité et la distributivité . Un exemple de corps fini est l'ensemble de 13 nombres {0, 1, 2, ..., 12} utilisant l'arithmétique modulaire . Dans ce domaine, le résultat de toute opération mathématique (addition, soustraction, multiplication ou division) est réduit modulo 13 ; c'est-à-dire que des multiples de 13 sont ajoutés ou soustraits jusqu'à ce que le résultat se situe dans la plage 0-12. Par exemple, le résultat de 5 × 7 = 35 mod 13 = 9. De tels corps finis peuvent être définis pour tout nombre premier p ; en utilisant des définitions plus complexes, elles peuvent également être définies pour chaque puissance m d'un premier p m . Les champs finis sont souvent appelés champs de Galois et sont abrégés en GF( p ) ou GF( p m ).   

Dans un tel corps à m nombres, tout élément non nul a a un unique inverse multiplicatif modulaire , a −1 tel que aa −1  =  a −1 a  ≡ 1 mod  m . Cet inverse peut être trouvé en résolvant l'équation de congruence ax  1 mod  m , ou l'équation diophantienne linéaire équivalente

hache + mon = 1.

Cette équation peut être résolue par l'algorithme d'Euclide, comme décrit ci - dessus . La recherche d'inverses multiplicatifs est une étape essentielle de l' algorithme RSA , largement utilisé dans le commerce électronique ; spécifiquement, l'équation détermine l'entier utilisé pour déchiffrer le message. Bien que l'algorithme RSA utilise des anneaux plutôt que des champs, l'algorithme euclidien peut toujours être utilisé pour trouver un inverse multiplicatif lorsqu'il existe. L'algorithme d'Euclide a aussi d'autres applications dans les codes correcteurs d'erreurs ; par exemple, il peut être utilisé comme alternative à l' algorithme de Berlekamp-Massey pour le décodage des codes BCH et Reed-Solomon , qui sont basés sur les champs de Galois.

théorème des restes chinois

L'algorithme d'Euclide peut également être utilisé pour résoudre plusieurs équations diophantiennes linéaires. De telles équations apparaissent dans le théorème des restes chinois , qui décrit une nouvelle méthode pour représenter un entier x . Au lieu de représenter un entier par ses chiffres, il peut être représenté par ses restes x i modulo un ensemble de N nombres premiers entre eux m i :

Le but est de déterminer x à partir de ses N restes x i . La solution consiste à combiner les équations multiples en une seule équation diophantienne linéaire avec un module M beaucoup plus grand qui est le produit de tous les modules individuels m i , et de définir M i comme

Ainsi, chaque M i est le produit de tous les modules sauf m i . La solution dépend de la recherche de N nouveaux nombres h i tels que

Avec ces nombres h i , tout entier x peut être reconstruit à partir de ses restes x i par l'équation

Puisque ces nombres h i sont les inverses multiplicatifs de M i , ils peuvent être trouvés en utilisant l'algorithme d'Euclide comme décrit dans la sous-section précédente.

Stern–Brocotier

L'algorithme euclidien peut être utilisé pour organiser l'ensemble de tous les nombres rationnels positifs dans un arbre de recherche binaire infini , appelé arbre de Stern-Brocot . Le nombre 1 (exprimé sous forme de fraction 1/1) est placé à la racine de l'arbre, et l'emplacement de tout autre nombre a / b peut être trouvé en calculant pgcd( a , b ) en utilisant la forme originale de l'algorithme d'Euclide , dans lequel chaque étape remplace le plus grand des deux nombres donnés par sa différence avec le plus petit nombre (pas son reste), s'arrêtant lorsque deux nombres égaux sont atteints. Une étape de l'algorithme d'Euclide qui remplace le premier des deux nombres correspond à une étape dans l'arbre d'un nœud à son enfant droit, et une étape qui remplace le deuxième des deux nombres correspond à une étape dans l'arbre à partir d'un nœud à son enfant gauche. La séquence d'étapes ainsi construite ne dépend pas du fait que a / b est donné dans les termes les plus bas, et forme un chemin de la racine à un nœud contenant le nombre a / b . Ce fait peut être utilisé pour prouver que chaque nombre rationnel positif apparaît exactement une fois dans cet arbre.

Par exemple, 3/4 peut être trouvé en partant de la racine, en allant une fois vers la gauche, puis deux fois vers la droite :

L'arbre de Stern-Brocot et les séquences de Stern-Brocot d'ordre i pour i = 1, 2, 3, 4

L'algorithme euclidien a presque la même relation avec un autre arbre binaire sur les nombres rationnels appelé arbre de Calkin-Wilf . La différence est que le chemin est inversé : au lieu de produire un chemin de la racine de l'arbre à une cible, il produit un chemin de la cible à la racine.

Fractions continues

L'algorithme euclidien a une relation étroite avec les fractions continues . La suite d'équations peut s'écrire sous la forme

Le dernier terme du membre de droite est toujours égal à l'inverse du membre de gauche de l'équation suivante. Ainsi, les deux premières équations peuvent être combinées pour former

La troisième équation peut être utilisée pour substituer le terme dénominateur r 1 / r 0 , ce qui donne

Le rapport final des restes r k / r k -1 peut toujours être remplacé à l'aide de l'équation suivante de la série, jusqu'à l'équation finale. Le résultat est une fraction continue

Dans l'exemple ci - dessus , le pgcd (1071, 462) a été calculé et les quotients q k étaient 2, 3 et 7, respectivement. Par conséquent, la fraction 1071/462 peut être écrite

comme cela peut être confirmé par le calcul.

Algorithmes de factorisation

Le calcul d' un plus grand commun diviseur est une étape essentielle dans plusieurs entier factorisation des algorithmes, tels que l'algorithme de rho de Pollard , l'algorithme de Shor , le procédé de factorisation de Dixon et la courbe elliptique Lenstra factorisation . L'algorithme d'Euclide peut être utilisé pour trouver efficacement ce GCD. La factorisation en fractions continues utilise des fractions continues, qui sont déterminées à l'aide de l'algorithme d'Euclide.

Efficacité algorithmique

"Un ensemble de lignes colorées rayonnant vers l'extérieur à partir de l'origine d'un système de coordonnées xy. Chaque ligne correspond à un ensemble de paires de nombres nécessitant le même nombre d'étapes dans l'algorithme euclidien."
Nombre d'étapes de l'algorithme d'Euclide pour pgcd( x , y ). Les points plus clairs (rouges et jaunes) indiquent relativement peu de pas, tandis que les points plus foncés (violets et bleus) indiquent plus de pas. La plus grande zone sombre suit la ligne y = Φx , où Φ est le nombre d' or .

L'efficacité de calcul de l'algorithme d'Euclide a été étudiée en profondeur. Cette efficacité peut être décrite par le nombre d'étapes de division que l'algorithme nécessite, multiplié par la dépense de calcul de chaque étape. La première analyse connue de l'algorithme d'Euclide est due à AAL Reynaud en 1811, qui montra que le nombre de pas de division en entrée ( u , v ) est borné par v ; plus tard, il a amélioré cela à v /2 + 2. Plus tard, en 1841, PJE Finck a montré que le nombre d'étapes de division est au plus de 2 log 2  v  + 1, et donc l'algorithme d'Euclide s'exécute en temps polynomial dans la taille de l'entrée. Émile Léger , en 1837, a étudié le pire des cas, c'est-à-dire lorsque les entrées sont des nombres de Fibonacci consécutifs . L'analyse de Finck a été affinée par Gabriel Lamé en 1844, qui a montré que le nombre d'étapes requises pour l'achèvement n'est jamais plus de cinq fois le nombre h de chiffres en base 10 du plus petit nombre  b .

Dans le modèle de coût uniforme (adapté à l'analyse de la complexité du calcul du pgcd sur des nombres qui tiennent dans un seul mot machine), chaque étape de l'algorithme prend un temps constant et l'analyse de Lamé implique que le temps d'exécution total est également O ( h ). Cependant, dans un modèle de calcul adapté au calcul avec des nombres plus grands, la dépense de calcul d'un seul calcul de reste dans l'algorithme peut être aussi grande que O ( h 2 ). Dans ce cas, le temps total pour toutes les étapes de l'algorithme peut être analysé à l'aide d'une série télescopique , montrant qu'il est également O ( h 2 ). Des techniques algorithmiques modernes basées sur l' algorithme de Schönhage-Strassen pour la multiplication rapide d'entiers peuvent être utilisées pour accélérer cela, conduisant à des algorithmes quasi-linéaires pour le GCD.

Nombre d'étapes

Le nombre d'étapes pour calculer le PGCD de deux nombres naturels, a et b , peut être noté T ( ab ). Si g est le PGCD de a et b , alors a  =  mg et b  =  ng pour deux nombres premiers entre m et n . Puis

T ( a , b ) = T ( m , n )

comme on peut le voir en divisant toutes les étapes de l'algorithme d'Euclide par g . Par le même argument, le nombre de pas reste le même si a et b sont multipliés par un facteur commun w : T ( a , b ) = T ( wa , wb ). Par conséquent, le nombre d'étapes T peut varier considérablement entre des paires de nombres voisines, telles que T( a , b ) et T( ab  +1), en fonction de la taille des deux GCD.

La nature récursive de l'algorithme d'Euclide donne une autre équation

T ( a , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = … = N + T ( r N −2 , r N −1 ) = N + 1

T ( x , 0) = 0 par hypothèse.

Pire cas

Si l'algorithme euclidien nécessite N étapes pour une paire d'entiers naturels a  >  b  > 0, les plus petites valeurs de a et b pour lesquelles cela est vrai sont les nombres de Fibonacci F N +2 et F N +1 , respectivement. Plus précisément, si l'algorithme d' Euclide nécessite N étapes pour la paire a  >  b , puis on a un  ≥  F N 2 et b  ≥  F N + 1 . Cela peut être démontré par induction . Si N  = 1, b divise a sans reste ; les plus petits nombres naturels pour lesquels cela est vrai sont b  = 1 et a  = 2, qui sont respectivement F 2 et F 3 . Supposons maintenant que le résultat soit valable pour toutes les valeurs de N jusqu'à M  − 1. La première étape de l' algorithme à M étapes est a  =  q 0 b  +  r 0 , et l'algorithme euclidien nécessite M  − 1 étapes pour la paire b  >  r 0 . Par hypothèse de récurrence, on a b  ≥  F M 1 et r 0  ≥  F M . Par conséquent, un  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  F M 1  +  F M  =  F M 2 , qui est l'inégalité désirée. Cette preuve, publiée par Gabriel Lamé en 1844, représente le début de la théorie de la complexité computationnelle , et aussi la première application pratique des nombres de Fibonacci.

Ce résultat suffit à montrer que le nombre d'étapes de l'algorithme d'Euclide ne peut jamais être supérieur à cinq fois le nombre de ses chiffres (base 10). En effet, si l'algorithme a besoin de N étapes, alors b est supérieur ou égal à F N 1 qui à son tour est supérieure ou égale à & phiv N -1 , où φ est le nombre d' or . Puisque b  ≥  φ N −1 , alors N  − 1 log φ b . Etant donné que log 10 φ  > 1/5, ( N  - 1) / 5 <log 10 φ  log φ b  = log 10 b . Ainsi, N  5 log 10 b . Ainsi, l'algorithme euclidien a toujours besoin de moins de O ( h ) divisions, où h est le nombre de chiffres dans le plus petit nombre b .

Moyenne

Le nombre moyen de pas effectués par l'algorithme d'Euclide a été défini de trois manières différentes. La première définition est le temps moyen T ( a ) nécessaire pour calculer le PGCD d'un nombre donné a et d'un nombre naturel plus petit b choisi avec une probabilité égale parmi les entiers 0 à a  − 1

Cependant, étant donné que T ( ab ) fluctue considérablement avec le PGCD des deux nombres, la fonction moyenne T ( a ) est également "bruyante".

Pour réduire ce bruit, une deuxième moyenne τ ( a ) est pris en charge tous les numéros premier avec un

Il existe φ ( a ) entiers premiers entre eux inférieurs à a , où φ est la fonction totient d'Euler . Cette moyenne tau croît doucement avec une

avec l'erreur résiduelle étant de l' ordre de - (6/1) + ε , où ε est infinitésimal . La constante C ( Constante de Porter ) dans cette formule est égale à

γ est la constante d'Euler–Mascheroni et ζ' est la dérivée de la fonction zêta de Riemann . Le coefficient dominant (12/π 2 ) ln 2 a été déterminé par deux méthodes indépendantes.

Puisque la première moyenne peut être calculée à partir de la moyenne tau en sommant sur les diviseurs d d'  un

il peut être approximé par la formule

où ( d ) est la fonction de Mangoldt .

Une troisième moyenne Y ( n ) est définie comme le nombre moyen d'étapes requises lorsque a et b sont choisis au hasard (avec une distribution uniforme) de 1 à n

La substitution de la formule approximative de T ( a ) dans cette équation donne une estimation de Y ( n )

Dépense de calcul par étape

A chaque étape k de l'algorithme euclidien, le quotient q k et le reste r k sont calculés pour une paire donnée d'entiers r k −2 et r k −1

r k -2 = q k r k -1 + r k .

La charge de calcul par étape est principalement associée à la découverte q k , puisque le reste r k peut être calculé rapidement de r k -2 , r k -1 , et q k

r k = r k −2q k r k −1 .

La charge de calcul de la division de h nombres -bit échelles comme O ( h ( 1)), où est la longueur du quotient.

À titre de comparaison, l'algorithme original basé sur la soustraction d'Euclide peut être beaucoup plus lent. Une seule division entière équivaut au quotient q du nombre de soustractions. Si le rapport de a et b est très grand, le quotient est grand et de nombreuses soustractions seront nécessaires. D'autre part, il a été montré que les quotients sont très probablement de petits entiers. La probabilité d'un quotient q donné est d'environ ln| u /( u  − 1)| où u  = ( q  + 1) 2 . À titre d'illustration, la probabilité d'un quotient de 1, 2, 3 ou 4 est d'environ 41,5 %, 17,0 %, 9,3 % et 5,9 %, respectivement. Étant donné que l'opération de soustraction est plus rapide que la division, en particulier pour les grands nombres, l'algorithme d'Euclide basé sur la soustraction est compétitif avec la version basée sur la division. Ceci est exploité dans la version binaire de l'algorithme d'Euclide.

La combinaison du nombre estimé d'étapes avec la dépense de calcul estimée par étape montre que l'algorithme d'Euclide croît de manière quadratique ( h 2 ) avec le nombre moyen de chiffres h dans les deux nombres initiaux a et b . Soit h 0 , h 1 , ..., h N −1 représentent le nombre de chiffres dans les restes successifs r 0r 1 , ...,  r N −1 . Comme le nombre d'étapes N croît linéairement avec h , le temps d'exécution est limité par

Méthodes alternatives

L'algorithme d'Euclide est largement utilisé dans la pratique, en particulier pour les petits nombres, en raison de sa simplicité. A titre de comparaison, l'efficacité des alternatives à l'algorithme d'Euclide peut être déterminée.

Une approche inefficace pour trouver le PGCD de deux nombres naturels a et b consiste à calculer tous leurs diviseurs communs ; le PGCD est alors le plus grand diviseur commun. Les diviseurs communs peuvent être trouvés en divisant les deux nombres par des nombres entiers successifs de 2 au plus petit nombre b . Le nombre d'étapes de cette approche croît linéairement avec b , ou exponentiellement dans le nombre de chiffres. Une autre approche inefficace consiste à trouver les facteurs premiers d'un ou des deux nombres. Comme indiqué ci - dessus , le PGCD est égal au produit des facteurs premiers partagés par les deux nombres a et b . Les méthodes actuelles de factorisation en nombres premiers sont également inefficaces ; de nombreux systèmes de cryptographie modernes reposent même sur cette inefficacité.

L' algorithme GCD binaire est une alternative efficace qui remplace la division par des opérations plus rapides en exploitant la représentation binaire utilisée par les ordinateurs. Cependant, cette alternative s'échelonne également comme O ( h ²) . Il est généralement plus rapide que l'algorithme d'Euclide sur des ordinateurs réels, même s'il évolue de la même manière. Une efficacité supplémentaire peut être glanée en examinant uniquement les premiers chiffres des deux nombres a et b . L'algorithme binaire peut être étendu à d'autres bases ( algorithmes k -aires), avec une vitesse jusqu'à cinq fois supérieure. L'algorithme GCD de Lehmer utilise le même principe général que l'algorithme binaire pour accélérer les calculs GCD dans des bases arbitraires.

Une approche récursive pour les très grands entiers (avec plus de 25 000 chiffres) conduit à des algorithmes GCD entiers quasi- linéaires, comme ceux de Schönhage, Stehlé et Zimmermann. Ces algorithmes exploitent la forme matricielle 2×2 de l'algorithme euclidien donné ci-dessus . Ces méthodes quasi-linéaires ont généralement une échelle de O ( h (log h ) 2 (log log h )).

Généralisations

Bien que l'algorithme euclidien soit utilisé pour trouver le plus grand diviseur commun de deux nombres naturels (entiers positifs), il peut être généralisé aux nombres réels et à d'autres objets mathématiques, tels que les polynômes , les entiers quadratiques et les quaternions de Hurwitz . Dans ces derniers cas, l'algorithme euclidien est utilisé pour démontrer la propriété cruciale de la factorisation unique, c'est-à-dire que de tels nombres peuvent être factorisés de manière unique en éléments irréductibles , les contreparties des nombres premiers. La factorisation unique est essentielle à de nombreuses preuves de la théorie des nombres.

Nombres rationnels et réels

L'algorithme d'Euclide peut être appliqué aux nombres réels , comme décrit par Euclide dans le livre 10 de ses Éléments . Le but de l'algorithme est d'identifier un nombre réel g tel que deux nombres réels donnés, a et b , soient des multiples entiers de celui-ci : a = mg et b = ng , où m et n sont des entiers . Cette identification revient à trouver une relation entière entre les nombres réels a et b ; c'est-à-dire qu'il détermine les entiers s et t tels que sa + tb = 0 . Euclid utilise cet algorithme pour traiter la question des longueurs incommensurables .

L'algorithme euclidien des nombres réels diffère de son homologue entier à deux égards. Premièrement, les restes r k sont des nombres réels, bien que les quotients q k soient des entiers comme précédemment. Deuxièmement, il n'est pas garanti que l'algorithme se termine par un nombre fini N d'étapes. Si c'est le cas, la fraction a / b est un nombre rationnel, c'est-à-dire le rapport de deux entiers

et peut s'écrire comme une fraction continue finie [ q 0 ; q 1 , q 2 , ..., q N ] . Si l'algorithme ne s'arrête pas, la fraction a / b est un nombre irrationnel et peut être décrit par une fraction continue infinie [ q 0 ; q 1 , q 2 , …] . Des exemples de fractions continues infinies sont le nombre d' or φ = [1; 1, 1, ...] et la racine carrée de deux , 2 = [1; 2, 2, ...] . Il est peu probable que l'algorithme s'arrête, car presque tous les rapports a / b de deux nombres réels sont irrationnels.

Une fraction continue infinie peut être tronquée au pas k [ q 0 ; q 1 , q 2 , ..., q k ] pour donner une approximation de a / b qui s'améliore à mesure que k augmente. L'approximation est décrite par les convergents m k / n k ; le numérateur et les dénominateurs sont premiers entre eux et obéissent à la relation de récurrence

m −1 = n −2 = 1 et m −2 = n −1 = 0 sont les valeurs initiales de la récursivité. Le convergent m k / n k est la meilleure approximation des nombres rationnels de a / b de dénominateur n k :

Polynômes

Les polynômes d'une seule variable x peuvent être additionnés, multipliés et factorisés en polynômes irréductibles , qui sont les analogues des nombres premiers pour les entiers. Le plus grand polynôme diviseur commun g ( x ) de deux polynômes a ( x ) et b ( x ) est défini comme le produit de leurs polynômes irréductibles partagés, qui peuvent être identifiés à l'aide de l'algorithme d'Euclide. La procédure de base est similaire à celle des nombres entiers. A chaque étape k , un polynôme quotient q k ( x ) et un polynôme reste r k ( x ) sont identifiés à satisfaire l'équation récursive

r −2 ( x ) = a ( x ) et r −1 ( x ) = b ( x ) . Chaque polynôme quotient est choisi de telle sorte que chaque reste soit nul ou ait un degré inférieur au degré de son prédécesseur : deg[ r k ( x )] < deg[ r k −1 ( x )] . Puisque le degré est un entier non négatif et qu'il diminue à chaque pas, l'algorithme d'Euclide conclut en un nombre fini de pas. Le dernier reste non nul est le plus grand diviseur commun des deux polynômes originaux, a ( x ) et b ( x ) .

Par exemple, considérons les deux polynômes quartiques suivants, qui se factorisent chacun en deux polynômes quadratiques

Diviser a ( x ) par b ( x ) donne un reste r 0 ( x ) = x 3 + (2/3) x 2 + (5/3) x − (2/3) . Dans l'étape suivante, b ( x ) est divisé par r 0 ( x ) donnant un reste r 1 ( x ) = x 2 + x + 2 . Enfin, la division de r 0 ( x ) par r 1 ( x ) donne un reste nul, indiquant que r 1 ( x ) est le plus grand polynôme diviseur commun de a ( x ) et b ( x ) , compatible avec leur factorisation.

La plupart des applications décrites ci-dessus pour les nombres entiers se répercutent sur les polynômes. L'algorithme euclidien peut être utilisé pour résoudre des équations diophantiennes linéaires et des problèmes de reste chinois pour les polynômes ; des fractions continues de polynômes peuvent également être définies.

L'algorithme polynomial euclidien a d'autres applications, telles que les chaînes de Sturm , une méthode pour compter les zéros d'un polynôme qui se trouvent à l'intérieur d'un intervalle réel donné . Cela a à son tour des applications dans plusieurs domaines, tels que le critère de stabilité Routh-Hurwitz dans la théorie du contrôle .

Enfin, les coefficients des polynômes n'ont pas besoin d'être tirés d'entiers, de nombres réels ou même de nombres complexes. Par exemple, les coefficients peuvent être tirés d'un champ général, tel que les champs finis GF( p ) décrits ci-dessus. Les conclusions correspondantes sur l'algorithme d'Euclide et ses applications sont valables même pour de tels polynômes.

Entiers gaussiens

"Un ensemble de points situés à l'intérieur d'un cercle. Le motif de points a une symétrie quadruple, c'est-à-dire que des rotations de 90 degrés laissent le motif inchangé. Le motif peut également être mis en miroir autour de quatre lignes passant par le centre du cercle : la verticale et l'horizontale axes, et les deux lignes diagonales à ±45 degrés."
Distribution des nombres premiers gaussiens u + vi dans le plan complexe, de normes u 2 + v 2 inférieures à 500

Les entiers gaussiens sont des nombres complexes de la forme α = u + vi , où u et v sont ordinaires entiers et i est la racine carrée de un négatif . En définissant un analogue de l'algorithme euclidien, on peut montrer que les entiers gaussiens sont factorisables de manière unique, par l'argument ci-dessus . Cette factorisation unique est utile dans de nombreuses applications, telles que la dérivation de tous les triplets de Pythagore ou la démonstration du théorème de Fermat sur les sommes de deux carrés . En général, l'algorithme euclidien est pratique dans de telles applications, mais pas essentiel ; par exemple, les théorèmes peuvent souvent être prouvés par d'autres arguments.

L'algorithme euclidien développé pour deux entiers gaussiens α et β est presque le même que celui pour les entiers ordinaires, mais diffère à deux égards. Comme précédemment, la tâche à chaque étape k est d'identifier un quotient q k et un reste r k de telle sorte que

r k −2 = α , où r k −1 = β , et où tout reste est strictement plus petit que son prédécesseur : | r k | < | r k −1 | . La première différence est que les quotients et les restes sont eux-mêmes des entiers gaussiens, et donc des nombres complexes . Le quotient q k sont généralement trouvées en arrondissant les parties réelles et complexes du rapport exact (tel que le nombre complexe α / β ) pour les nombres entiers les plus proches. La seconde différence réside dans la nécessité de définir comment un reste complexe peut être « plus petit » qu'un autre. Pour ce faire, une fonction de norme f ( u + vi ) = u 2 + v 2 est définie, qui convertit chaque entier gaussien u + vi en un entier ordinaire. Après chaque étape k de l'algorithme d'Euclide, la norme du reste f ( r k ) est inférieure à la norme du reste précédent, f ( r k -1 ) . Puisque la norme est un entier non négatif et diminue à chaque pas, l'algorithme euclidien pour les entiers gaussiens se termine par un nombre fini d'étapes. Le reste final non nul est pgcd( α , β ) , l'entier gaussien de plus grande norme qui divise à la fois α et β ; il est unique à la multiplication par une unité près, ±1 ou ± i .

La plupart des autres applications de l'algorithme d'Euclide portent sur les entiers gaussiens. Par exemple, il peut être utilisé pour résoudre des équations diophantiennes linéaires et des problèmes de restes chinois pour des entiers gaussiens ; des fractions continues d'entiers gaussiens peuvent également être définies.

Domaines euclidiens

Un ensemble d'éléments sous deux opérations binaires , notées addition et multiplication, est appelé domaine euclidien s'il forme un anneau commutatif R et, grosso modo, si un algorithme euclidien généralisé peut leur être appliqué. Les deux opérations d'un tel anneau n'ont pas besoin d'être l'addition et la multiplication de l'arithmétique ordinaire ; elles peuvent plutôt être plus générales, telles que les opérations d'un groupe mathématique ou d'un monoïde . Néanmoins, ces opérations générales doivent respecter de nombreuses lois régissant l'arithmétique ordinaire, telles que la commutativité , l' associativité et la distributivité .

L'algorithme euclidien généralisé nécessite une fonction euclidienne , c'est-à-dire une application f de R dans l'ensemble des entiers non négatifs tels que, pour deux éléments non nuls a et b dans R , il existe q et r dans R tels que a = qb + r et f ( r ) < f ( b ) . Des exemples de tels mappages sont la valeur absolue pour les entiers, le degré pour les polynômes univariés et la norme pour les entiers gaussiens ci-dessus . Le principe de base est que chaque étape de l'algorithme réduit f inexorablement; par conséquent, si f ne peut être réduit qu'un nombre fini de fois, l'algorithme doit s'arrêter en un nombre fini d'étapes. Ce principe repose sur la propriété de bon ordre des entiers non négatifs, qui affirme que chaque ensemble non vide d'entiers non négatifs a un plus petit membre.

Le théorème fondamental de l'arithmétique s'applique à tout domaine euclidien : tout nombre d'un domaine euclidien peut être factorisé de manière unique en éléments irréductibles . Tout domaine euclidien est un domaine de factorisation unique (UFD), bien que l'inverse ne soit pas vrai. Les domaines euclidiens et les UFD sont des sous-classes des domaines GCD , domaines dans lesquels un plus grand commun diviseur de deux nombres existe toujours. En d'autres termes, un plus grand diviseur commun peut exister (pour toutes les paires d'éléments d'un domaine), bien qu'il ne soit pas possible de le trouver à l'aide d'un algorithme euclidien. Un domaine euclidien est toujours un domaine idéal principal (PID), un domaine intégral dans lequel chaque idéal est un idéal principal . Encore une fois, l'inverse n'est pas vrai : tous les PID ne sont pas un domaine euclidien.

La factorisation unique des domaines euclidiens est utile dans de nombreuses applications. Par exemple, la factorisation unique des entiers gaussiens est pratique pour dériver des formules pour tous les triplets de Pythagore et pour prouver le théorème de Fermat sur les sommes de deux carrés . La factorisation unique était également un élément clé dans une tentative de preuve du dernier théorème de Fermat publiée en 1847 par Gabriel Lamé, le même mathématicien qui a analysé l'efficacité de l'algorithme d'Euclide, sur la base d'une suggestion de Joseph Liouville . L'approche de Lamé nécessitait la factorisation unique des nombres de la forme x + ωy , où x et y sont des nombres entiers, et ω = e 2 / n est une racine n ième de 1, c'est-à-dire ω n = 1 . Bien que cette approche réussisse pour certaines valeurs de n (telles que n = 3 , les entiers d'Eisenstein ), en général de tels nombres ne sont pas factorisés de manière unique. Cet échec de la factorisation unique dans certains champs cyclotomiques a conduit Ernst Kummer au concept de nombres idéaux et, plus tard, Richard Dedekind aux idéaux .

Factorisation unique des entiers quadratiques

"Un ensemble de points situés à l'intérieur d'un cercle. Le motif de points a une symétrie sextuple, c'est-à-dire que des rotations de 60 degrés laissent le motif inchangé. Le motif peut également être mis en miroir sur six lignes passant par le centre du cercle : la verticale et l'horizontale axes, et les quatre lignes diagonales à ±30 et ±60 degrés."
Distribution des nombres premiers d'Eisenstein u + dans le plan complexe, avec des normes inférieures à 500. Le nombre ω est une racine cubique de 1 .

Les anneaux entiers quadratiques sont utiles pour illustrer les domaines euclidiens. Les entiers quadratiques sont des généralisations des entiers gaussiens dans lesquels l' unité imaginaire i est remplacée par un nombre ω . Ainsi, ils ont la forme u + , où u et v sont des nombres entiers et ω a l'une des deux formes, en fonction d'un paramètre D . Si D n'est pas égal à un multiple de quatre plus un, alors

Si, toutefois, D est égal à un multiple de quatre plus un, alors

Si la fonction f correspond à une fonction de norme , telle que celle utilisée pour ordonner les entiers gaussiens ci - dessus , alors le domaine est dit norm-euclidien . Les anneaux euclidiens normés des entiers quadratiques sont exactement ceux où D est l'une des valeurs -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19 , 21, 29, 33, 37, 41, 57 ou 73. Les cas D = −1 et D = −3 donnent respectivement les entiers gaussiens et les entiers d'Eisenstein .

Si f est autorisé à être n'importe quelle fonction euclidienne, alors la liste des valeurs possibles de D pour lesquelles le domaine est euclidien n'est pas encore connue. Le premier exemple d'un domaine euclidien qui n'était pas norm-euclidien (avec D = 69 ) a été publié en 1994. En 1973, Weinberger a prouvé qu'un anneau entier quadratique avec D > 0 est euclidien si, et seulement si, c'est un principal domaine idéal , à condition que l' hypothèse de Riemann généralisée soit vérifiée .

Anneaux non commutatifs

L'algorithme euclidien peut être appliqué à certains anneaux non commutatifs tels que l'ensemble des quaternions de Hurwitz . Soit α et ß représentent deux éléments de bague d'un tel. Ils ont un diviseur commun droite δ si α = ξδ et β = ηδ pour certains choix de ξ et η dans l'anneau. De même, ils ont un diviseur commun gauche si α = et β = pour certains choix de ξ et η dans l'anneau. Comme la multiplication n'est pas commutative, il existe deux versions de l'algorithme d'Euclide, une pour les diviseurs droits et une pour les diviseurs gauches. En choisissant les bons diviseurs, la première étape pour trouver le pgcd( α , β ) par l'algorithme d'Euclide peut être écrite

ψ 0 représente le quotient et p 0 le reste. Cette équation montre que tout diviseur droit commun de α et β est également un diviseur commun du reste p 0 . L'équation analogue pour les diviseurs de gauche serait

Quel que soit le choix, le processus est répété comme ci-dessus jusqu'à ce que le plus grand diviseur commun droit ou gauche soit identifié. Comme dans le domaine euclidien, la "taille" du reste ρ 0 (formellement, sa norme ) doit être strictement inférieure à β , et il ne doit y avoir qu'un nombre fini de tailles possibles pour ρ 0 , de sorte que l'algorithme est garanti à mettre fin.

La plupart des résultats du PGCD sont reportés sur des nombres non commutatifs. Par exemple, l'identité de Bézout stipule que le pgcd droit ( α , β ) peut être exprimé comme une combinaison linéaire de α et β . En d' autres termes, il y a un nombre σ et T pour telle que

L'identité analogue pour le PGCD gauche est presque la même :

L'identité de Bézout peut être utilisée pour résoudre des équations diophantiennes. Par exemple, l'une des preuves standard du théorème des quatre carrés de Lagrange , selon lequel chaque entier positif peut être représenté comme une somme de quatre carrés, est basée sur les PGCD de quaternions de cette manière.

Voir également

  • Rythme euclidien , une méthode d'utilisation de l'algorithme euclidien pour générer des rythmes musicaux

Remarques

Les références

Bibliographie

Liens externes