Calculateur de PGCD - Plus grand commun diviseur

Le plus grand commun diviseur (PGCD), aussi appelé greatest common factor (GCF), greatest common divisor (GCD) ou highest common factor (HCF), est le plus grand entier positif qui divise chacun des entiers d’un ensemble donné sans reste. Par exemple, le PGCD de 12 et 18 est 6, car 6 est le plus grand nombre qui divise exactement 12 et 18. Les deux algorithmes les plus courants pour calculer le PGCD sont l’algorithme d’Euclide et la factorisation première. L’algorithme d’Euclide est le plus efficace des deux pour les grands nombres. Il fonctionne en remplaçant de façon répétée la paire (a, b) par (b, a mod b) jusqu’à ce que le reste soit 0 ; la dernière valeur non nulle de b est le PGCD. L’algorithme s’exécute en O(log min(a,b)) étapes, ce qui le rend extrêmement rapide même pour de très grands entiers. La factorisation première calcule le PGCD en exprimant chaque nombre comme un produit de puissances de nombres premiers, puis en prenant le produit de chaque nombre premier élevé à la puissance minimale trouvée dans tous les nombres. Par exemple, 12 = 2^2 * 3 et 18 = 2 * 3^2, donc PGCD(12, 18) = 2^1 * 3^1 = 6. Bien que moins efficace que l’algorithme d’Euclide pour les grands nombres, la factorisation première offre une explication pédagogique claire de la valeur du PGCD. Le PGCD a de nombreuses applications pratiques. En arithmétique, il sert à réduire les fractions à leur forme irréductible : pour simplifier a/b, divisez le numérateur et le dénominateur par PGCD(a, b). En géométrie, le PGCD de deux longueurs donne la plus grande règle qui mesure les deux sans reste. En informatique, le PGCD apparaît dans l’arithmétique modulaire, les algorithmes cryptographiques (comme la génération de clés RSA) et la compression de données. Pour plus de deux nombres, le PGCD se calcule de manière itérative. PGCD(a, b, c) = PGCD(PGCD(a, b), c). Ce calculateur accepte n’importe quel nombre d’entiers positifs et prend en charge l’algorithme d’Euclide (pour des résultats rapides) ainsi que la factorisation première (pour une sortie détaillée étape par étape). La vue par factorisation première est particulièrement utile aux élèves qui apprennent les facteurs et la divisibilité.