Processus itératif de division qui calcule le plus grand commun diviseur (pgcd) de deux entiers en remplaçant à répétition le plus grand par le reste de la division par le plus petit jusqu'à obtention d'un reste nul.

Principe

pgcd(a,b) = pgcd(b, a mod b) ; l'application répétée de cette réduction diminue la taille des opérandes et se termine sur le pgcd lorsque le reste devient nul.

Démonstration

Calcul de pgcd(48, 18) : 48 = 2·18 + 12, 18 = 1·12 + 6, 12 = 2·6 + 0, donc pgcd(48,18) = 6. L'algorithme étendu fournit des coefficients x,y tels que 48x + 18y = 6.

Mauvaise application

Appliquer l'algorithme à des non-entiers sans structure de division euclidienne ou supposer des performances indépendantes de la taille des opérandes sont des usages erronés ; il faut aussi gérer correctement entrées négatives ou nulles.

Conséquence

L'algorithme d'Euclide fournit une méthode efficace pour le calcul du pgcd, sert au calcul d'inverses modulaires et à la détermination des coefficients de Bezout via l'algorithme étendu, et se généralise aux domaines euclidiens.

Inversion

Recourir à la factorisation en nombres premiers pour calculer le pgcd est l'approche inverse conceptuelle ; la factorisation donne le pgcd mais est souvent beaucoup moins efficace pour de grands entiers que la réduction euclidienne.

Limite

S'applique aux entiers et à tout domaine euclidien muni d'un algorithme de division avec reste ; il ne s'applique pas directement aux anneaux arbitraires dépourvus de norme euclidienne ni à des objets sans opération de reste définie.

Tension sémantique

Comparer l'algorithme d'Euclide aux algorithmes binaires de pgcd et aux méthodes basées sur la factorisation : Euclide minimise par les restes via division, les binaires exploitent l'arithmétique binaire, la factorisation utilise la décomposition en facteurs premiers.

Synthèse

L'algorithme d'Euclide réduit systématiquement un problème de pgcd par divisions successives jusqu'à terminaison, offrant une procédure efficace et généralisable qui fournit aussi des combinaisons linéaires exprimant le pgcd.