Le PGCD de 109.900.009.163 et 199.742.422.931, quel est le plus grand commun diviseur ? Déterminer le plus grand facteur commun (différent de zéro)

Calculer le PGCD (109.900.009.163 ; 199.742.422.931), quel est le plus grand commun diviseur ? Méthodes utilisées : 1. La décomposition en facteurs premiers. 2. L'algorithme d'Euclide

Le plus grand commun diviseur et comment est-il calculé ?

Premiers pas et exemples

  • 1. Facteurs d'un nombre :
    • Les facteurs d'un nombre sont les nombres multipliés entre eux pour obtenir ce nombre.
    • Exemples : 2 × 3 × 4 = 24 ; 4 × 9 = 36.
    • Dans ces cas, nous disons que 2, 3 et 4 sont des facteurs de 24. Et 4 et 9 sont des facteurs de 36.
  • 2. Facteurs communs de plusieurs nombres :
    • Les facteurs communs à plusieurs nombres sont appelés facteurs communs.
    • Dans nos exemples, 4 est à la fois un facteur de 24 et de 36.
  • 3. Le plus grand commun diviseur, PGCD, de plusieurs nombres
    • Le plus grand facteur commun, PGCD, est le plus grand de tous les facteurs communs de ces différents nombres.
  • 4. Comment le plus grand commun diviseur est-il calculé ? Étape 1.
    • Dans nos exemples, nous pourrions être tentés de dire que 4 est le plus grand commun diviseur de 24 et 36. Mais, attendez. Essayons de diviser ces facteurs en facteurs aussi petits que possible.
    • 24 pourrait s'écrire comme : 24 = 2 × 2 × 2 × 3.
    • 36 pourrait également s'écrire comme : 36 = 2 × 2 × 3 × 3.
    • Dans notre exemple, 2 et 3 ne peuvent pas être décomposés en d'autres nombres plus petits.
  • 5. Nombres premiers :
    • 2 et 3 ne peuvent pas être décomposés en d'autres nombres plus petits car ce sont des nombres premiers. C'est la définition même des nombres premiers :
    • Un nombre premier n'a pas d'autres facteurs que 1 et lui-même car il ne peut pas être décomposé en d'autres nombres plus petits.
    • Exemples de nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, etc., c'est une liste infinie.
  • 6. Comment calcule-t-on le plus grand commun diviseur, PGCD ? Étape 2.
    • Nous avons vu qu'il est judicieux de décomposer les nombres en facteurs aussi petits que possible, en les écrivant comme un produit de facteurs premiers. C'est la définition de la décomposition d'un nombre en facteurs premiers.
    • La décomposition en facteurs premiers de 24 = 2 × 2 × 2 × 3 = 23 × 3.
    • La décomposition en facteurs premiers de 36 = 2 × 2 × 3 × 3 = 22 × 32.
    • Pour calculer le PGCD, il suffit de choisir tous les facteurs premiers communs des deux nombres et de les multiplier :
    • PGCD (24 et 36) = 2 × 2 × 3 = 22 × 3 = 12.

Calculer le plus grand commun diviseur
pgcd (109.900.009.163; 199.742.422.931) = ?

Méthode 1. La décomposition en facteurs premiers (la factorisation première):

La décomposition en facteurs premiers (la factorisation première) d'un nombre : trouver les nombres premiers qui se multiplient ensemble pour former ce nombre.


109.900.009.163 = 7 × 71 × 221.126.779
109.900.009.163 n'est pas un nombre premier mais un composé.

199.742.422.931 = 37 × 67 × 80.573.789
199.742.422.931 n'est pas un nombre premier mais un composé.



Calculer le plus grand commun diviseur:

Multipliez tous les facteurs premiers communs, pris par leurs plus petites puissances (exposants).

Mais les deux nombres n'ont pas de facteurs premiers communs.


Le plus grand commun diviseur,
pgcd (109.900.009.163; 199.742.422.931) = 1
Nombres premiers entre eux.
Faites défiler vers le bas pour la 2ème méthode...

Méthode 2. L'algorithme d'Euclide:

  • Cet algorithme implique le processus de division des nombres et de calcul des restes.
  • 'a' et 'b' sont les deux nombres naturels, 'a' >= 'b'.
  • Divisez 'a' par 'b' et obtenez le reste de l'opération, 'r'.
  • Si 'r' = 0, STOP. 'b' = le PGCD de 'a' et 'b'.
  • Sinon : Remplacez ('a' par 'b') et ('b' par 'r'). Revenez à l'étape ci-dessus..

  • » L'algorithme d'Euclide



Étape 1. Divisez le plus grand nombre par le plus petit:
199.742.422.931 : 109.900.009.163 = 1 + 89.842.413.768
Étape 2. Divisez le plus petit nombre par le reste de l'opération ci-dessus:
109.900.009.163 : 89.842.413.768 = 1 + 20.057.595.395
Étape 3. Diviser le reste de l'étape 1 par le reste de l'étape 2:
89.842.413.768 : 20.057.595.395 = 4 + 9.612.032.188
Étape 4. Diviser le reste de l'étape 2 par le reste de l'étape 3:
20.057.595.395 : 9.612.032.188 = 2 + 833.531.019
Étape 5. Diviser le reste de l'étape 3 par le reste de l'étape 4:
9.612.032.188 : 833.531.019 = 11 + 443.190.979
Étape 6. Diviser le reste de l'étape 4 par le reste de l'étape 5:
833.531.019 : 443.190.979 = 1 + 390.340.040
Étape 7. Diviser le reste de l'étape 5 par le reste de l'étape 6:
443.190.979 : 390.340.040 = 1 + 52.850.939
Étape 8. Diviser le reste de l'étape 6 par le reste de l'étape 7:
390.340.040 : 52.850.939 = 7 + 20.383.467
Étape 9. Diviser le reste de l'étape 7 par le reste de l'étape 8:
52.850.939 : 20.383.467 = 2 + 12.084.005
Étape 10. Diviser le reste de l'étape 8 par le reste de l'étape 9:
20.383.467 : 12.084.005 = 1 + 8.299.462
Étape 11. Diviser le reste de l'étape 9 par le reste de l'étape 10:
12.084.005 : 8.299.462 = 1 + 3.784.543
Étape 12. Diviser le reste de l'étape 10 par le reste de l'étape 11:
8.299.462 : 3.784.543 = 2 + 730.376
Étape 13. Diviser le reste de l'étape 11 par le reste de l'étape 12:
3.784.543 : 730.376 = 5 + 132.663
Étape 14. Diviser le reste de l'étape 12 par le reste de l'étape 13:
730.376 : 132.663 = 5 + 67.061
Étape 15. Diviser le reste de l'étape 13 par le reste de l'étape 14:
132.663 : 67.061 = 1 + 65.602
Étape 16. Diviser le reste de l'étape 14 par le reste de l'étape 15:
67.061 : 65.602 = 1 + 1.459
Étape 17. Diviser le reste de l'étape 15 par le reste de l'étape 16:
65.602 : 1.459 = 44 + 1.406
Étape 18. Diviser le reste de l'étape 16 par le reste de l'étape 17:
1.459 : 1.406 = 1 + 53
Étape 19. Diviser le reste de l'étape 17 par le reste de l'étape 18:
1.406 : 53 = 26 + 28
Étape 20. Diviser le reste de l'étape 18 par le reste de l'étape 19:
53 : 28 = 1 + 25
Étape 21. Diviser le reste de l'étape 19 par le reste de l'étape 20:
28 : 25 = 1 + 3
Étape 22. Diviser le reste de l'étape 20 par le reste de l'étape 21:
25 : 3 = 8 + 1
Étape 23. Diviser le reste de l'étape 21 par le reste de l'étape 22:
3 : 1 = 3 + 0
A cette étape, le reste est nul, donc on s'arrête:
1 est le nombre que nous recherchions - le dernier reste non nul.
C'est le plus grand commun diviseur.


Le plus grand commun diviseur:
pgcd (109.900.009.163; 199.742.422.931) = 1
Nombres premiers entre eux.
Les deux nombres n'ont pas de facteurs premiers en commun


Pourquoi doit-on calculer le plus grand commun diviseur ?


Opérations similaires avec le calcul du PGCD, le plus grand commun diviseur :

» Le PGCD de 109.900.009.169 et 199.742.422.952, quel est le plus grand commun diviseur ? Déterminer le plus grand facteur commun (différent de zéro)

» Opérations mensuelles : Valeurs calculées du plus grand commun diviseur, pgcd

» Mois 04, 2026 [Avril] : Valeurs calculées du plus grand commun diviseur, pgcd


Partager

Le plus grand commun diviseur, pgcd. Qu'est-ce que c'est et comment le calculer

  • Note : La décomposition d'un nombre en facteurs premiers (la factorisation première d'un nombre) consiste à écrire un nombre naturel supérieur à 1 sous la forme d'un produit de nombres premiers.
  • Supposons que le nombre "t" divise le nombre "a" sans reste.
  • Lorsque nous examinons la factorisation première de "a" et "t", nous constatons que :
  • 1) tous les facteurs premiers de "t" sont aussi des facteurs premiers de "a"
  • et
  • 2) les exposants (puissances) des facteurs premiers de "t" sont égaux ou inférieurs aux exposants des facteurs premiers de "a" (voir la * note ci-dessous)
  • Par exemple, le nombre 12 est un diviseur du nombre 60 :
  • 12 = 2 × 2 × 3 = 22 × 3
  • 60 = 2 × 2 × 3 × 5 = 22 × 3 × 5
  • * Note: 23 = 2 × 2 × 2 = 8. On dit 2 à la puissance 3 - ou - 2 exposant 3. Dans cet exemple, 3 est l'exposant et 2 la base. L'exposant indique combien de fois la base est multipliée par elle-même. 23 est la puissance et 8 est la valeur de la puissance.
  • Si le nombre "t" est un diviseur commun des nombres "a" et "b", alors :
  • 1) "t" n'a que des facteurs premiers qui interviennent également dans la factorisation première de "a" et "b".
  • et
  • 2) chaque facteur premier de "t" a les plus petits exposants par rapport aux facteurs premiers des nombres "a" et "b".
  • Par exemple, le nombre 12 est le diviseur commun des nombres 48 et 360. Voici ci-dessous leur factorisation première :
  • 12 = 22 × 3
  • 48 = 24 × 3
  • 360 = 23 × 32 × 5
  • Vous pouvez voir que le nombre 12 n'a que les facteurs premiers qui se produisent également dans la décomposition en facteurs premiers des nombres 48 et 360.
  • Vous pouvez voir ci-dessus que les nombres 48 et 360 contiennent plusieurs facteurs communs : 2, 3, 4, 6, 8, 12, 24. Parmi ceux-ci, 24 est le plus grand commun diviseur (pgcd) de 48 et 360.
  • 24 = 2 × 2 × 2 × 3 = 23 × 3
  • 48 = 24 × 3
  • 360 = 23 × 32 × 5
  • 24, le plus grand diviseur commun des nombres 48 et 360, est calculé comme le produit de tous les facteurs premiers communs des deux nombres, pris par les plus petits exposants (puissances).
  • Si deux nombres "a" et "b" n'ont pas d'autre diviseur commun que 1, pgcd (a, b) = 1, alors les nombres "a" et "b" sont appelés nombres premiers entre eux.
  • Si "a" et "b" ne sont pas premiers entre eux, alors chaque diviseur commun de "a" et "b" est un diviseur du plus grand commun diviseur de "a" et "b".
  • Prenons un exemple sur la façon de calculer le plus grand commun diviseur, pgcd, des nombres suivants :
  • 1.260 = 22 × 32
  • 3.024 = 24 × 32 × 7
  • 5.544 = 23 × 32 × 7 × 11
  • pgcd (1.260, 3.024, 5.544) = 22 × 32 = 252
  • Et un autre exemple :
  • 900 = 22 × 32 × 52
  • 270 = 2 × 33 × 5
  • 210 = 2 × 3 × 5 × 7
  • pgcd (900, 270, 210) = 2 × 3 × 5 = 30
  • Et encore un exemple :
  • 90 = 2 × 32 × 5
  • 27 = 33
  • 22 = 2 × 11
  • pgcd (90, 27, 22) = 1 - Les trois nombres n'ont pas de facteurs premiers en commun, ils sont premiers entre eux.