Qu'est-ce que l'algorithme d'Euclide ?
L'algorithme d'Euclide compte parmi les plus anciens algorithmes connus : il a été décrit par le mathématicien grec Euclide vers 300 av. J.-C. Il permet de déterminer efficacement le plus grand commun diviseur (PGCD) de deux entiers, autrement dit le plus grand nombre qui divise les deux sans laisser de reste. Ce calculateur fournit également le plus petit commun multiple (PPCM), qui se déduit directement du PGCD.
Comment utiliser ce calculateur
Saisissez deux nombres entiers dans les champs ci-dessus, puis validez. Le calculateur travaille sur les valeurs absolues de vos données et applique de façon répétée la règle \(\gcd(\text{a}, \text{b}) = \gcd(\text{b}, \text{a} \bmod \text{b})\) jusqu'à ce que le reste atteigne zéro. Il affiche ensuite à la fois le PGCD et le PPCM.
La formule expliquée
L'idée centrale est que le PGCD de deux nombres ne change pas si l'on remplace le plus grand par le reste de sa division par le plus petit. Sous forme symbolique :
$$\gcd\!\left(\text{a},\,\text{b}\right) = \gcd\!\left(\text{b},\,\text{a} \bmod \text{b}\right)$$On répète l'opération jusqu'à ce que \(\text{b} = 0\) ; la dernière valeur non nulle est le PGCD. Le PPCM se calcule alors par
$$\operatorname{lcm}\!\left(\text{a},\,\text{b}\right) = \frac{\left|\text{a}\right| \times \left|\text{b}\right|}{\gcd\!\left(\text{a},\,\text{b}\right)}$$puisque le produit de deux nombres est égal au produit de leur PGCD et de leur PPCM.
Exemple détaillé
Calculons \(\gcd(48, 36)\) : \(48 \bmod 36 = 12\), donc \(\gcd(36, 12)\). Ensuite \(36 \bmod 12 = 0\), le PGCD est donc 12. Le PPCM vaut
$$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
Questions fréquentes
Que se passe-t-il si l'un des nombres est nul ? \(\gcd(\text{a}, 0) = \text{a}\). L'algorithme gère ce cas naturellement : la boucle s'arrête aussitôt et renvoie la valeur non nulle.
L'ordre de a et b a-t-il une importance ? Non. \(\gcd(\text{a}, \text{b}) = \gcd(\text{b}, \text{a})\) ; l'algorithme se corrige de lui-même dès la première étape.
Puis-je utiliser des nombres négatifs ? Oui. Le calculateur prend les valeurs absolues, car le PGCD est par convention défini comme un nombre positif.
