Calculateur PGCD | Plus Grand Commun Diviseur

Le calculateur PGCD évalue le plus grand commun diviseur entre deux à quinze nombres différents. Poursuivez votre lecture pour savoir quel est le plus grand commun diviseur de deux nombres donnés, et découvrez plusieurs méthodes pour déterminer le PGCD, notamment la factorisation des nombres premiers ou l'algorithme d'Euclide ; choisissez celle que vous préférez et vérifiez par vous-même que notre calculateur PGCD peut vous faire gagner du temps lorsque vous traitez de grands nombres !

La définition du plus grand commun diviseur est le plus grand facteur ou diviseur entier présent dans un ensemble de nombres. Il est important pour certaines applications mathématiques telles que la simplification des polynômes où il est souvent essentiel de trouver les facteurs communs, et ensuite le PGCD.

Il existe plusieurs méthodes pour vous aider à trouver le PGCD. Certaines sont un jeu d'enfant, d'autres sont plus complexes. C'est mieux de toutes les connaître pour pouvoir choisir celle que vous préférez. Nous avons donc :

• l'utilisation de la liste des facteurs ou diviseurs ;
• la factorisation des nombres premiers ;
• l'algorithme d'Euclide ;
• l'algorithme binaire (l'algorithme de Stein) ;
• l'utilisation de plusieurs propriétés du PGCD (y compris le plus petit commun multiple, PPCM).

La bonne nouvelle, c'est que vous pouvez estimer le PGCD à l'aide d'opérations mathématiques simples, sans racines ni logarithmes ! Dans la plupart des cas, il s'agit simplement d'une soustraction, d'une multiplication ou d'une division.

La principale méthode utilisée pour estimer le plus grand diviseur commun consiste à trouver tous les facteurs 🇺🇸 des nombres donnés. Les facteurs ou diviseurs sont simplement des nombres qui sont multipliés ensemble pour obtenir la valeur originale. En général, ils peuvent être positifs ou négatifs, par exemple, 2 × 3 est la même chose que (-2) × (-3), les deux étant égaux à 6. D'un point de vue pratique, nous ne considérons que les nombres positifs. De plus, seuls les entiers sont concernés. Sinon, vous pourriez trouver une combinaison infinie de fractions distinctes étant des facteurs, ce qui est inutile dans notre cas. Sachant cela, estimons le plus grand dénominateur commun des nombres 72 et 40.

1. Les facteurs de 72 sont : 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
2. Les facteurs de 40 sont : 1, 2, 4, 5, 8, 10, 20, 40.
3. Énumérez tous les facteurs communs : 1, 2, 4, 8.
4. Le plus grand diviseur commun est 8, la plus grande valeur ci-dessus.

Essayons quelque chose de plus difficile. Nous voulons trouver la réponse à cette question : « Quel est le plus grand commun diviseur de 33 264 et 35 640 ? ». Tout ce que nous avons à faire, c'est de répéter les étapes précédentes :

1. Les facteurs de 33 264 sont : 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1 008, 1 188, 1 232, 1 386, 1 512, 1 584, 1 848, 2 079, 2 376, 2 772, 3 024, 3 696, 4 158, 4 752, 5 544, 8 316, 11 088, 16 632, 33 264.

2. Les facteurs de 35 640 sont : 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1 080, 1 188, 1 320, 1 485, 1 620, 1 782, 1 980, 2 376, 2 970, 3 240, 3 564, 3 960, 4 455, 5 940, 7 128, 8 910, 11 880, 17 820, 35 640.

3. Liste de tous les diviseurs communs : 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1 188, 2 376.

4. Le résultat final est le suivant : 2 376.

Comme vous pouvez le constater, plus le nombre de diviseurs est élevé, plus la procédure prend du temps et il est facile de se tromper. Il est utile de savoir comment fonctionne cette méthode, mais nous vous recommandons d'utiliser notre calculateur PGCD pour vous assurer que le résultat est correct.

Une autre procédure couramment utilisée est la factorisation des nombres premiers 🇺🇸. Cette méthode est quelque peu liée à celle mentionnée précédemment. Au lieu d'énumérer tous les facteurs possibles, nous ne trouvons que ceux qui sont des nombres premiers. Par conséquent, le produit de tous les nombres premiers qui sont les mêmes pour les deux nombres est la réponse à notre problème. De plus, il y a toujours une façon unique de factoriser n'importe quel nombre en nombres premiers. Maintenant, trouvons le plus grand commun diviseur de 72 et 40 en utilisant la factorisation des nombres premiers :

1. Les nombres premiers qui factorisent 72 sont : 2, 2, 2, 3, 3.

2. Les nombres premiers qui factorisent 40 sont : 2, 2, 2, 5.

3. En d'autres termes, nous pouvons écrire : 72 = 2 × 2 × 2 × 3 × 3 et 40 = 2 × 2 × 2 × 5.

4. La partie en commun est 2 × 2 × 2 = 8, et c'est le plus grand diviseur commun.

Nous pouvons voir que pour cet exemple simple, le résultat est cohérent avec la méthode précédente. Voyons si elle fonctionne aussi bien pour le cas plus compliqué. Quel est le PGCD de 33 264 et 35 640 ?

1. Les nombres premiers qui factorisent 33 264 sont : 2, 2, 2, 2, 3, 3, 3, 7, 11.

2. Les nombres premiers qui factorisent 35 640 sont :2, 2, 2, 3, 3, 3, 3, 5, 11.

3. Nous pouvons utiliser la notation en exposant pour écrire les produits comme suit : 33 264 = 2⁴ × 3³ × 7 × 11, 35 640 = 2³ × 3⁴ × 5 × 11.

4. Le produit commun de deux nombres est 2³ × 3³ × 11. Nous pouvons également l'écrire de manière plus compacte et plus sophistiquée, en prenant en compte les factorielles : (3!)³ × 11. Vérifiez si notre calculateur PGCD vous donne le même résultat, à savoir 2 376.

L'idée, qui est à la base de l'algorithme d'Euclide, dit que si le nombre k est le plus grand commun diviseur des nombres A et B, alors k est aussi le PGCD pour la différence de ces nombres A - B. En suivant cette procédure, nous atteindrons finalement 0. Par conséquent, le plus grand commun diviseur est le dernier nombre non nul. Jetons un coup d'œil encore une fois à nos exemples : les nombres 40 et 72. Chaque fois que nous effectuons une soustraction, nous comparons deux nombres, en les classant de la plus grande à la plus petite valeur :

• PGCD de 72 et 40 : la différence de 72 - 40 est égale à 32 ;
• PGCD de 40 et 32 : 40 - 32 = 8 ;
• PGCD de 32 et 8 : 32 - 8 = 24 ;
• PGCD de 24 et 8 : 24 - 8 = 16 ;
• PGCD de 16 et 8 : 16 - 8 = 8 ;
• PGCD de 8 et 8 : 8 - 8 = 0 STOP !

Dans notre dernière étape, nous obtenons 0 par soustraction. Cela signifie que nous trouvons notre plus grand diviseur commun et sa valeur dans l'avant-dernière ligne : 8.

Qu'en est-il d'un cas plus difficile avec 33 264 et 35 640 ? Essayons de le résoudre en utilisant l'algorithme d'Euclide :

• PGCD de 35 640 et 33 264 : 35 640 - 33 264 = 2 376 ;
• PGCD de 33 264 et 2 376 : 33 264 - 2 376 = 30 888 ;
• PGCD de 30 888 et 2 376 : 30 888 - 2 376 = 28 512 ;
• PGCD de 28 512 et 2 376 : 28 512 - 2 376 = 26 136 ;
• PGCD de 26136 et 2 376 : 26 136 - 2 376 = 23 760 ;
• PGCD de 23 760 et 2 376 : 23 760 - 2 376 = 21 384 ;
• PGCD de 21 384 et 2 376 : 21 384 - 2 376 = 19 008 ;
• PGCD de 19 008 et 2 376 : 19 008 - 2 376 = 16 632 ;
• PGCD de 16 632 et 2 376 : 16 632 - 2 376 = 14 256 ;
• PGCD de 14 256 et 2 376 : 14 256 - 2 376 = 11 880 ;
• PGCD de 11 880 et 2 376 : 11 880 - 2 376 = 9 504 ;
• PGCD de 9 504 et 2 376 : 9 504 - 2 376 = 7 128 ;
• PGCD de 7 128 et 2 376 : 7 128 - 2 376 = 4 752 ;
• PGCD de 4 752 et 2 376 : 4 752 - 2 376 = 2 376 ;
• PGCD de 2 376 et 2 376 : 2 376 - 2 376 = 0 STOP !

Comme dans l'exemple précédent, le PGCD de 33 264 et 35 640 est la dernière différence non nulle de la procédure, qui est 2 376.

Comme vous pouvez le constater, cette méthode pour trouver le PGCD est très efficace et simple, mais elle présente un inconvénient important. Plus la différence entre les nombres donnés est importante, plus le nombre d'étapes nécessaires pour atteindre l'étape finale est élevé. Le modulo est une opération mathématique efficace qui résout le problème, car nous ne nous intéressons qu'à un reste plus petit que les deux nombres. Répétons l'algorithme euclidien pour nos exemples en utilisant le modulo au lieu de la soustraction ordinaire :

• PGCD de 72 et 40 : 72 mod 40 = 32 ;
• PGCD de 40 et 32 : 40 mod 32 = 8 ;
• PGCD de 32 et 8 : 32 mod 8 = 0 STOP !

Le plus grand dénominateur commun est 8. Qu'en est-il de l'autre ?

• PGCD de 35 640 et 33 264 : 35 640 mod 33 264 = 2 376 ;
• PGCD de 33 264 et 2 376 : 33 264 mod 2 376 = 0 STOP !

Le PGCD de 35 640 et 33 264 est 2 376, et il a été trouvé en seulement deux étapes au lieu de 15. Pas mal, non ?

Si vous aimez les opérations arithmétiques plus simples que celles utilisées dans l'algorithme d'Euclide (par exemple modulo), l'algorithme binaire (ou algorithme de Stein) est définitivement fait pour vous ! Il vous suffit d'utiliser la comparaison, la soustraction et la division par 2. Lorsque vous estimez le plus grand commun diviseur de deux nombres, gardez à l'esprit ces identités :

1. PGCD(A, 0) = A, nous utilisons le fait que chaque nombre divise zéro, que l'un des nombres tombe à zéro, et que notre résultat était le précédent (vu dans la dernière étape de l'algorithme d'Euclide)

2. Si A et B sont tous deux pairs, cela signifie que PGCD(A, B) = 2 × PGCD(A/2, B/2) en raison du fait que 2 est un facteur commun.

3. Si un seul des nombres est pair, disons A, alors PGCD(A, B) = PGCD(A/2, B). Cette fois-ci, 2 n'est pas un diviseur commun, nous pouvons donc poursuivre la réduction jusqu'à ce que les deux nombres soient impairs.

4. Si A et B sont tous deux impairs et A > B, alors PGCD(A, B) = PGCD((A-B)/2, B). Cette fois, nous combinons deux caractéristiques en une seule étape. La première est dérivée de l'algorithme d'Euclide, qui calcule le plus grand commun diviseur de la différence des deux nombres et du plus petit. Deuxièmement, la division par 2 est possible puisque la différence de deux nombres impairs est paire et que, conformément à l'étape 3, nous pouvons réduire le nombre pair.

5. Les étapes 2 à 4 sont répétées jusqu'à l'étape 1 ou si A = B. Le résultat sera 2ⁿ × A, où n est le nombre de facteurs 2 trouvés dans une deuxième étape.

Comme d'habitude, pratiquons l'algorithme avec nos ensembles de nombres. Commençons par 40 et 72.

• Ils sont tous les deux pairs, donc PGCD(72, 40) = 2 × PGCD36, 20) = 2² × PGCD(18, 10) = 2³ × PGCD(9, 5) = ....

• Les nombres restants sont impairs, donc ... = 2³ × PGCD((9-5)/2, 5) = 2³ × PGCD(2, 5).

• 2 est pair, nous pouvons donc le réduire : ... = 2³ × PGCD(1, 5).

• 1 et 5 sont impairs donc : ... = 2³ × PGCD((5-1)/2, 1) = 2³ × PGCD(2, 1).

• Enlever 2 à un nombre pair : ... = 2³ × PGCD(1, 1) = 2³ = 8.

En fait, nous aurions pu nous arrêter à la troisième étape puisque le PGCD de 1 et de n'importe quel nombre est 1.
D'accord, et comment trouver le plus grand facteur commun diviseur de 33 264 et 35 640 en utilisant la méthode binaire ?

• Deux nombres pairs : PGCD(35 640, 33 264) = 2 × PGCD(17 820, 16 632) = 2² × PGCD(8 910, 8 316) = 2³ × PGCD(4 455, 4 158) = ....

• Un pair, un impair : ... = 2³ × PGCD(4 455, 2 079).

• Deux impairs : ... = 2³ × PGCD((4 455-2 079)/2, 2 079) = 2³ × PGCD(1 188, 2 079).

• Un pair, un impair : ... = 2³ × PGCD(594, 2 079) = 2³ × PGCD(297, 2 079).

• Deux impairs : ... = 2³ × PGCD((2 079-2 97)/2, 297) = 2³ × PGCD(891, 297).

• Deux impairs : ... = 2³ × PGCD((891-297)/2, 297) = 2³ × PGCD(297, 297) = 2³ × 297 = 2 376.

Nous savons que les nombres premiers sont ceux qui n'ont que 2 facteurs entiers positifs : 1 et eux-mêmes. La question est donc de savoir ce que sont les nombres premiers entre eux. Nous pouvons les définir comme les nombres qui n'ont pas de facteurs communs. Plus précisément, 1 est leur seul facteur commun, mais comme nous omettons 1 dans la factorisation des nombres premiers, on peut dire qu'ils n'ont pas de diviseur commun. En d'autres termes, nous pouvons écrire que les nombres A et B sont premiers entre eux si PGCD(A,B) = 1. Cela ne signifie pas vraiment que l'un ou l'autre est un nombre premier, mais simplement que la liste des facteurs communs est vide. Les exemples de nombres premiers entre eux sont : 5 et 7, 35 et 48, 23 156 et 44 613.

Un fait amusant : il est possible de calculer la probabilité que deux nombres choisis au hasard soient premiers entre eux. Bien que ce soit assez compliqué, le résultat global est d'environ 61 %. Êtes-vous surpris·e ? Testez-le vous-même : imaginez deux nombres aléatoires (disons d'au moins 5 chiffres), utilisez notre calculateur du plus grand commun diviseur et vérifiez si le résultat est égal à 1 ou non. Répétez le jeu plusieurs fois et estimez le pourcentage de nombres premiers entre eux que vous avez trouvé.

Maintenant que nous connaissons de nombreuses méthodes pour trouver le plus grand commun diviseur de deux nombres, vous pouvez vous demander : comment trouver le plus grand commun diviseur de trois nombres ou plus ?. Il s'avère que ce n'est pas aussi difficile qu'il n'y paraît au premier coup d'œil. En effet, l'énumération de tous les facteurs de chaque nombre est une méthode simple, puisqu'il suffit de trouver le plus grand d'entre eux. Cependant, vous pouvez rapidement vous rendre compte que cela devient de plus en plus fastidieux à mesure que le nombre de chiffres augmente.

La méthode de factorisation des nombres premiers présente un inconvénient similaire, mais comme nous pouvons regrouper tous les nombres premiers par ordre croissant, par exemple, nous pouvons introduire un moyen d'obtenir un résultat un peu plus rapidement qu'auparavant.

D'autre part, si vous préférez utiliser des algorithmes binaires ou euclidiens pour estimer quel est le PGCD de plusieurs nombres, vous pouvez également utiliser un théorème qui stipule que :

PGCD(a, b, c) = PGCD(PGCD(a, b), c) = PGCD(PGCD(a, c), b) = PGCD(PGCD(b, c), a)

Cela signifie que nous pouvons calculer le PGCD de deux nombres quelconques, puis refaire la méthode de l'algorithme en utilisant le résultat et le troisième nombre et continuer tant qu'il reste des chiffres. Le choix des deux premiers n'a pas d'importance.

Un autre concept étroitement lié au PGCD est le plus petit commun multiple (PPCM). Pour trouver le plus petit commun multiple, nous utilisons en grande partie le même processus que celui utilisé pour trouver le PGCD. Une fois les nombres réduits à la factorisation des nombres premiers, nous recherchons la puissance la plus petite de chaque facteur, plutôt que la puissance la plus grande. Nous multiplions ensuite les puissances les plus petites et le résultat est le plus petit commun multiple ou PPCM. Cette opération peut être effectuée à la main ou en utilisant le calculateur PPCM.

Le plus grand facteur commun diviseur peut être estimé en utilisant le PPCM. L'expression suivante est valide :

PGCD(a, b) = |a × b| / PPCM(a, b)

Il peut être pratique de trouver d'abord le plus petit commun multiple en raison de la complexité et de la durée. Naturellement, il peut être calculé de l'une ou l'autre manière, il est donc utile de savoir à la fois comment trouver le PGCD et le PPCM.

Nous avons déjà présenté quelques propriétés du plus grand commun diviseur. Dans cette section, nous énumérons les plus importantes d'entre elles :

• Si le rapport de deux nombres entiers a et b (a > b) est un entier, alors PGCD(a, b) = b.

• PGCD(a, 0) = a, utilisé dans l'algorithme d'Euclide.

• PGCD(a, 1) = 1.

• Si a et b n'ont pas de facteurs communs (ils sont premiers entre eux), alors PGCD(a, b) = 1.

• Tous les facteurs communs de a et b sont aussi des diviseurs de PGCD(a,b).

• Si b × c / a est un entier et PGCD(a, b) = d, alors a × c / d est aussi un entier.

• Pour tout entier k : PGCD(k×a, k×b) = k × PGCD(a, b), utilisé dans l'algorithme binaire.

• Pour tout entier positif k : PGCD(a/k, b/k) = PGCD(a, b) / k.

• PGCD(a, b) × PPCM(a, b) = |a×b|.

• PGCD(a, PPCM(b, c)) = PPCM(PGCD(a, b), PGCD(a, c)).

• PPCM(a, PGCD(b, c)) = PGCD(PPCM(a, b), PPCM(a, c)).

Non, le PGCD de 14 et 42 n'est pas 2. Le PGCD de 14 et 42 est 14, et pour le trouver, décomposez les deux nombres en leurs facteurs :

• les facteurs de 14 sont 1, 2, 7 et 14 ; et
• les facteurs de 42 sont 1, 2, 3, 6, 7, 14, 21 et 42.

Comme vous pouvez le constater, le plus grand nombre commun aux deux listes est 14, qui est le PGCD.

Le PGCD de 8 et 12 est 4. Pour arriver à cette réponse :

1. Écrivez tous les facteurs de tous les nombres :

   • les facteurs de 8 sont 1, 2, 4 et 8 ; et
   • les facteurs de 12 sont 1, 2, 3, 4, 6 et 12.

2. Citez tous les facteurs communs : 1, 2, 4.

3. Le plus grand facteur commun est le plus grand d'entre eux, soit 4.

Le PGCD de 24 et 36 est 12. Nous pouvons obtenir cette réponse en utilisant la méthode euclidienne :

1. Classez les nombres par ordre croissant :

   24, 36.

2. Effectuez l'opération modulo en prenant le plus grand nombre comme dividende et le plus petit comme diviseur :

   36 mod 24 = 12.

3. Rassemblez le diviseur et le reste et classez-les par ordre croissant :

   12, 24.

4. Effectuez à nouveau l'opération modulo de la même manière :

   24 mod 12 = 0.

5. Il ne reste qu'un seul nombre (le diviseur, 12), donc 12 est le plus grand commun diviseur.

Le PGCD de 30 et 54 est 6. On peut utiliser la factorisation des nombres premiers pour obtenir la réponse :

1. Écrivez tous les nombres sous la forme d'un produit de leurs facteurs premiers :

   • 30 = 2 × 3 × 5
   • 54 = 2 × 3 × 3 × 3

2. Citez tous les facteurs qui sont premiers en communs : 2, 3.

3. Trouvez le produit de tous les facteurs qui sont premiers et communs : 2 × 3 = 6

4. Le plus grand commun diviseur est le résultat de l'étape précédente. Pour 30 et 54, il s'agit de 6.