Calculateur de PGCD – Plus Grand Commun Diviseur

Quel est le plus grand facteur commun (PGC) ?

Le plus grand facteur commun (PGC) — également appelé plus grand diviseur commun (PGD) ou plus grand facteur commun (PHC) — est le plus grand entier positif qui divise deux ou plusieurs nombres sans laisser de reste. Il s'agit d'un concept fondamental en théorie des nombres et a des applications pratiques dans la simplification des fractions, la résolution de problèmes de mots et la répartition d'objets en groupes égaux.

Par exemple, les facteurs de 24 sont : 1, 2, 3, 4, 6, 8, 12, 24. Les facteurs de 36 sont : 1, 2, 3, 4, 6, 9, 12, 18, 36. Les facteurs communs sont : 1, 2, 3, 4, 6, 12. Le plus grand de ceux-ci est 12, donc PGC(24, 36) = 12.

Le PGC est lié au plus petit multiple commun (LMC) par l'identité fondamentale : PGC(a, b) × LMC(a, b) = a × b. Cela signifie que si vous connaissez le PGC, vous pouvez calculer rapidement le LMC, et vice versa. Pour 24 et 36 : PGC = 12, LMC = 24 × 36/12 = 72.

Méthodes pour trouver le PGC

Il existe trois méthodes principales pour trouver le PGC. Chacune a ses avantages en fonction de la taille des nombres impliqués.

Méthode 1 : Liste des facteurs

Énumérez tous les facteurs de chaque nombre, puis identifiez le plus grand commun. Cela fonctionne bien pour les petits nombres mais devient fastidieux pour les grands.

Exemple : PGC(18, 24). Facteurs de 18 : 1, 2, 3, 6, 9, 18. Facteurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24. Communs : 1, 2, 3, 6. PGC = 6.

Méthode 2 : Factorisation première

Exprimez chaque nombre comme produit de facteurs premiers, puis multipliez les facteurs premiers communs (en utilisant l'exposant le plus bas pour chaque).

Exemple : PGC(120, 180). 120 = 2³ × 3 × 5. 180 = 2² × 3² × 5. Facteurs premiers communs : 2² × 3 × 5 = 4 × 3 × 5 = 60. PGC(120, 180) = 60.

Méthode 3 : Algorithme d'Euclide

L'algorithme d'Euclide est la méthode la plus efficace, surtout pour les grands nombres. Il repose sur la propriété selon laquelle PGC(a, b) = PGC(b, a mod b). Répétez jusqu'à ce que le reste soit 0 ; le dernier reste non nul est le PGC.

Exemple : PGC(252, 105). Étape 1 : 252 = 2 × 105 + 42. Étape 2 : 105 = 2 × 42 + 21. Étape 3 : 42 = 2 × 21 + 0. PGC = 21.

Table de référence PGC : Pairs de nombres fréquemment utilisés

Ces valeurs PGC sont pour les paires de nombres fréquemment utilisées dans les problèmes de mathématiques et la simplification des fractions :

Remarquez que lorsque PGC(a, b) = b, b divise a sans reste. Lorsque PGC(a, b) = 1, les nombres sont premiers entre eux — ils n'ont pas de facteurs communs autres que 1. Les nombres premiers entre eux sont importants en cryptographie, en particulier dans l'algorithme RSA où choisir des nombres premiers entre eux est essentiel pour la génération de clés.

Simplifier des fractions en utilisant le PGCD

La principale utilisation courante du PGCD est la simplification des fractions en termes les plus bas. Pour simplifier une fraction a/b, divisez à la fois le numérateur et le dénominateur par le PGCD(a, b).

Exemples :

• 48/60 : PGCD(48, 60) = 12. → 48 ÷ 12 / 60 ÷ 12 = 4/5 ✓
• 56/84 : PGCD(56, 84) = 28. → 56 ÷ 28 / 84 ÷ 28 = 2/3 ✓
• 75/100 : PGCD(75, 100) = 25. → 75 ÷ 25 / 100 ÷ 25 = 3/4 ✓
• 144/360 : PGCD(144, 360) = 72. → 144 ÷ 72 / 360 ÷ 72 = 2/5 ✓

Une fraction est en termes les plus bas (forme la plus simple) lorsque PGCD(numerator, dénominateur) = 1. Par exemple, 3/5 est déjà en termes les plus bas car PGCD(3, 5) = 1. La fraction 6/10 n'est pas en termes les plus bas car PGCD(6, 10) = 2 → 3/5.

En cuisine, le PGCD aide à échelonner les recettes. Si une recette sert 24 mais vous voulez servir 18, vous avez besoin de 18/24 = 3/4 de chaque ingrédient. PGCD(18, 24) = 6, donc 18/24 → 3/4. Multipliez toutes les quantités par 3/4.

PGCD dans les applications du monde réel

Au-delà de la simplification des fractions, le PGCD résout plusieurs types de problèmes pratiques :

Égalisation de groupes : Vous avez 36 pommes et 48 oranges à mettre dans des paniers, avec chaque panier contenant le même nombre de chaque fruit et sans fruit en trop. Le nombre maximum de paniers est PGCD(36, 48) = 12. Chaque panier reçoit 3 pommes et 4 oranges.

Problèmes de tuiles/grille : Vous voulez recouvrir un plancher de 120 cm × 180 cm avec des tuiles carrées identiques, minimisant les déchets. La plus grande tuile carrée qui fonctionne parfaitement a une longueur de côté PGCD(120, 180) = 60 cm. Vous avez besoin de (120/60) × (180/60) = 2 × 3 = 6 tuiles.

Planification : L'événement A se répète tous les 12 jours, l'événement B tous les 18 jours. Ils se produisent à nouveau ensemble après LCM(12, 18) = 36 jours. PGCD(12, 18) = 6 vous indique le cycle unitaire ; LCM = 12 × 18/6 = 36.

Cryptographie : L'algorithme RSA nécessite de choisir deux nombres premiers p et q. La clé publique n = p × q et l'éuler totient φ(n) = (p-1) × (q-1). Pour que l'algorithme fonctionne de manière sécurisée, l'exposant de chiffrement e doit être premier avec φ(n) — c'est-à-dire, PGCD(e, φ(n)) = 1. La coprimauté est vérifiée à l'aide de l'algorithme euclidien.

L'algorithme d'Euclide : Histoire et Preuve

L'algorithme d'Euclide, décrit dans les Éléments d'Euclide (Livre VII, Proposition 2, c. 300 avant JC), est l'un des plus anciens algorithmes de la mathématique — il précède la plupart des mathématiques modernes de plus de deux mille ans. Il reste largement utilisé aujourd'hui en calcul, témoignant de son élégance et de son efficacité.

L'algorithme : Trouver GCF(a, b) où a > b : diviser a par b, obtenir le quotient q et le reste r. Ensuite, GCF(a, b) = GCF(b, r). Répéter jusqu'à r = 0 ; le dernier reste non nul est le GCF.

Pourquoi cela fonctionne : Si d divise à la fois a et b, alors d divise a − q×b = r. À l'inverse, si d divise à la fois b et r, alors d divise b×q + r = a. Par conséquent, l'ensemble des diviseurs communs de (a, b) est égal à l'ensemble des diviseurs communs de (b, r). Leurs GCF doivent être égaux.

Efficacité : Dans le pire des cas (nombres de Fibonacci consécutifs), l'algorithme prend O(log(min(a,b))) étapes. GCF(F(n+1), F(n)) nécessite exactement n étapes — c'est pourquoi les nombres de Fibonacci consécutifs sont appelés le "pire des cas" pour l'algorithme d'Euclide. Pour GCF(144, 89) : 144 = 1×89 + 55 ; 89 = 1×55 + 34 ; 55 = 1×34 + 21 ; 34 = 1×21 + 13 ; 21 = 1×13 + 8 ; 13 = 1×8 + 5 ; 8 = 1×5 + 3 ; 5 = 1×3 + 2 ; 3 = 1×2 + 1 ; 2 = 2×1 + 0. GCF = 1. (10 étapes, comme prévu pour F(12)/F(11).)

GCF vs LCM : Principales différences et connexions

GCF (Facteur commun le plus élevé) et LCM (Multiple le plus petit commun) sont des opérations complémentaires. Comprendre quand utiliser l'une ou l'autre est essentiel pour l'arithmétique des fractions.

Pour ajouter les fractions 1/12 + 1/18 : trouver LCM(12, 18) = 36. Convertir : 3/36 + 2/36 = 5/36. Pour simplifier 12/18 : trouver GCF(12, 18) = 6. Diviser : 2/3.

Algorithme euclidien étendu et identité de Bézout

L'algorithme euclidien étendu ne calcule pas seulement le PGCD(a, b) mais trouve également des entiers x et y tels que ax + by = PGCD(a, b). C'est l'identité de Bézout, et les entiers x et y s'appellent les coefficients de Bézout. Cela a des applications critiques en arithmétique modulaire et en cryptographie.

Exemple : Trouvez x et y tels que 24x + 36y = PGCD(24, 36) = 12. En travaillant à rebours à travers les étapes de l'algorithme euclidien : 12 = 24 − 1×12 = 24 − 1×(36 − 1×24) = 2×24 − 1×36. Donc x = 2, y = -1. Vérifiez : 24×2 + 36×(−1) = 48 − 36 = 12 ✓.

L'inverse modulaire d'un nombre a modulo m existe si et seulement si PGCD(a, m) = 1. Si elle existe, elle peut être trouvée à l'aide de l'algorithme euclidien étendu. Par exemple, l'inverse de 7 mod 11 : PGCD(7, 11) = 1 (relativement premier), donc l'inverse existe. 7×8 = 56 = 5×11 + 1 ≡ 1 (mod 11), donc 7⁻¹ ≡ 8 (mod 11). C'est fondamental pour la décryptage RSA et de nombreuses opérations cryptographiques.

PGCD pour des fractions, des ratios et des proportions

Le PGCD est indispensable lors du travail avec des ratios et des proportions dans des contextes quotidiens. Un ratio comme 48:64 peut être simplifié en divisant les deux termes par PGCD(48, 64) = 16, ce qui donne le ratio équivalent 3:4. Cette simplification facilite les comparaisons et révèle la relation sous-jacente.

En pâtisserie et en cuisine, les recettes nécessitent souvent d'être échelonnées. Si une recette demande 450g de farine et 300g de sucre, le ratio est 450:300. PGCD(450, 300) = 150. Ratio simplifié : 3:2. Pour toute taille de lot, utilisez de la farine et du sucre dans un ratio de 3:2.

Les échelles de cartes utilisent des ratios. Une échelle de 1:50 000 signifie 1 unité de carte = 50 000 unités réelles. Si vous voulez exprimer une mesure de 150cm sur la carte comme une distance réelle de 75 000cm, simplifiez 150:75 000. PGCD(150, 75000) = 150. Ratio simplifié : 1:500. Donc l'échelle de la carte est 1:500 pour cette mesure.