Qu'est-ce que l'algorithme d'Euclide ?
L'algorithme d'Euclide est l'un des plus anciens algorithmes connus, décrit par le mathématicien grec Euclide vers 300 av. J.-C. Il permet de trouver le plus grand commun diviseur (PGCD) de deux nombres entiers, c'est-à-dire le plus grand nombre qui divise les deux sans laisser de reste. Ce calculateur applique l'algorithme à n'importe quels deux entiers positifs ou nuls et fournit également leur plus petit commun multiple (PPCM).
Comment l'utiliser
Saisissez vos deux nombres dans les champs a et b, puis validez. Le calculateur affiche le PGCD comme résultat principal et le PPCM comme valeur secondaire. L'ordre n'a aucune importance : \(\gcd(48, 36) = \gcd(36, 48)\). Les nombres négatifs sont pris en compte par leur valeur absolue, et si l'un des nombres vaut 0, le PGCD correspond tout simplement à l'autre nombre.
La formule expliquée
L'algorithme repose sur une idée toute simple : tout diviseur commun à a et b divise aussi leur reste a mod b. On remplace donc à chaque étape le plus grand nombre par ce reste :
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$
Chaque étape réduit rapidement la taille des nombres, si bien que même des valeurs gigantesques se résolvent en quelques itérations seulement. Le PPCM se calcule ensuite par $$\operatorname{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$$
Exemple détaillé
Calculons \(\gcd(48, 36)\) :
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$
Le PGCD vaut donc 12, et le PPCM $$= \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
Questions fréquentes
Que se passe-t-il si les deux nombres valent 0 ? Le PGCD de 0 et 0 est ici défini comme 0, et le PPCM vaut également 0 puisqu'il n'existe aucun multiple positif commun.
Pourquoi est-ce plus rapide que de lister les diviseurs ? Au lieu de chercher tous les diviseurs, l'algorithme utilise le raccourci du reste, ce qui réduit considérablement la taille du problème à chaque étape — un temps généralement logarithmique.
Peut-il traiter de très grands nombres ? Oui. L'algorithme d'Euclide reste efficace même pour des nombres comportant de nombreux chiffres, car il ne nécessite qu'un petit nombre d'opérations modulo.
