Calculateur de PGCD

Le plus grand commun diviseur de deux nombres entiers est le plus grand entier qui les divise tous les deux exactement, et il apparaît constamment : pour réduire des fractions, répartir des quantités en groupes égaux, dimensionner le carrelage d'un sol ou simplifier des rapports dans le code. Cette capacité le calcule avec l'algorithme d'Euclide, la même méthode que les mathématiciens utilisent depuis plus de deux mille ans, et renvoie un seul entier. Envoyez deux entiers — positifs, négatifs ou nuls, sous forme de nombres ou de chaînes numériques exactes — et recevez leur plus grand commun diviseur.

Ce qu'est réellement le plus grand commun diviseur

Prenez deux entiers, disons 48 et 18. Les nombres qui divisent exactement 48 sont 1, 2, 3, 4, 6, 8, 12, 16, 24 et 48 ; les diviseurs de 18 sont 1, 2, 3, 6, 9 et 18. Les diviseurs qu'ils partagent sont 1, 2, 3 et 6, et le plus grand d'entre eux — 6 — est le plus grand commun diviseur, noté pgcd(48, 18) = 6.

Énumérer les diviseurs fonctionne pour les petits nombres, mais cela passe très mal à l'échelle : factoriser un entier de quinze chiffres est réellement difficile. Le calculateur de plus grand commun diviseur évite entièrement la factorisation. Il utilise l'algorithme d'Euclide, qui repose sur une observation : tout diviseur commun de a et b divise aussi le reste de la division du plus grand par le plus petit.

Remplacer le plus grand nombre par ce reste réduit le problème à chaque étape tout en conservant tous les diviseurs communs, jusqu'à ce que l'un des nombres atteigne zéro et que l'autre soit la réponse. Le calcul complet prend au plus quelques dizaines d'étapes, même pour les plus grands entiers que JavaScript représente exactement, et le résultat est toujours exact — pas de virgule flottante, pas d'approximation.

Entrées, signes, zéro et erreurs

Le point d'accès accepte deux champs obligatoires, a et b. Les signes n'ont aucune importance : pgcd(-48, 18) est égal à pgcd(48, 18), car un diviseur d'un nombre divise aussi son opposé, donc l'algorithme travaille sur les valeurs absolues.

Zéro est une entrée légitime avec un sens précis — pgcd(17, 0) vaut 17, puisque tout entier divise zéro et que le plus grand diviseur de 17 est 17 lui-même — mais les deux champs à zéro sont rejetés, car tout entier divise zéro et il n'en existe pas de plus grand. Les valeurs absolues sont limitées à 9007199254740991, le plus grand entier que JavaScript représente exactement ; toute valeur supérieure ne pourrait pas être traitée exactement et est refusée.

Où elle s'intègre et combien elle coûte

Vous rencontrez le plus grand commun diviseur plus souvent que son nom ne le suggère. Réduire une fraction à ses plus petits termes consiste à diviser le numérateur et le dénominateur par leur PGCD. Répartir une expédition en cartons identiques sans rien laisser de côté, choisir le plus grand carreau carré qui couvre un sol rectangulaire sans découpe et simplifier un rapport d'aspect dans une mise en page adaptative sont la même question sous des habits différents.

Dans le code, il apparaît dans les planificateurs, les fonctions de hachage et les routines cryptographiques. Cette capacité est volontairement minimale : elle renvoie le facteur lui-même, rien d'autre, de sorte qu'elle se compose proprement avec tout ce qui le consomme. Si vous avez besoin des étapes de division complètes de l'algorithme d'Euclide, des coefficients de Bézout ou aussi du plus petit commun multiple, des capacités sœurs couvrent ces besoins.

Elle s'exécute sur notre edge mondial sans rien conserver après la réponse, et le même module alimente le calculateur gratuit de cette page, de sorte que vous pouvez vérifier n'importe quel résultat à la main avant de l'intégrer à un pipeline.