Algorithme d'Euclide

En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule efficacement le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, c'est-à-dire qu'ils sont tous les deux multiples de celui-ci. C'est un des plus anciens algorithmes connus, mais il reste toujours d'actualité.

L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres.