##  [Algorithme Euclidien](/fr/node/61981) 

 Définition

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

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

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

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

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

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

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

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

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.