Qu'est-ce que l'algorithme d'Euclide permet de calculer ?

L’algorithme d’Euclide est une méthode classique de l’arithmétique qui permet de calculer le plus grand commun diviseur, ou PGCD, de deux nombres entiers. Le PGCD est le plus grand entier qui divise ces deux nombres sans laisser de reste. Décrit dans les Éléments d’Euclide, ouvrage associé au mathématicien grec Euclide d’Alexandrie et généralement daté de l’Antiquité grecque, cet algorithme reste utilisé en mathématiques comme en informatique.

Une succession de divisions

Son principe repose sur une propriété des diviseurs communs : le PGCD de deux nombres ne change pas lorsque l’on remplace le plus grand par le reste de sa division par le plus petit. On effectue donc des divisions successives jusqu’à ce que le reste soit nul. Le dernier reste non nul correspond alors au PGCD. Cette méthode fonctionne parce que les diviseurs communs du dividende et du diviseur sont exactement les mêmes que ceux du diviseur et du reste.

Un exemple concret

Pour calculer le PGCD de 252 et de 105, on commence par écrire 252 = 2 × 105 + 42. On poursuit avec 105 = 2 × 42 + 21, puis 42 = 2 × 21 + 0. Le dernier reste non nul est 21 : le PGCD de 252 et de 105 vaut donc 21. La procédure peut être appliquée à n’importe quelle paire d’entiers, en prenant au besoin leurs valeurs absolues lorsque des nombres négatifs sont concernés.

Simplifier des fractions

Le calcul du PGCD est notamment utile pour réduire une fraction à sa forme irréductible. Il suffit de diviser le numérateur et le dénominateur par leur PGCD. Ainsi, la fraction 252/105 devient 12/5 après division de ses deux termes par 21. En programmation, cette même procédure permet de traiter rapidement des nombres entiers et d’éviter des recherches successives parmi tous leurs diviseurs.

Un outil toujours utilisé en informatique

L’algorithme d’Euclide est particulièrement efficace : le nombre de divisions nécessaires augmente de manière logarithmique avec la taille du plus petit nombre initial, ce qui le rend adapté aux entiers très grands. Sa version étendue permet en outre de trouver des coefficients entiers vérifiant l’identité de Bézout, de la forme au + bv = PGCD(a,b). Cette extension est importante en théorie des nombres et intervient notamment dans le calcul d’inverses modulaires, utilisé dans certains procédés de cryptographie comme RSA.