Contenu

• Pas
• Méthode 1 sur 2: Algorithme de diviseur
• Méthode 2 sur 2: Facteurs premiers
• Conseils

Le plus grand diviseur commun (GCD) de deux entiers est le plus grand entier qui divise chacun de ces nombres. Par exemple, le pgcd pour 20 et 16 est 4 (les deux 16 et 20 ont de grands diviseurs, mais ils ne sont pas communs - par exemple, 8 est un diviseur de 16, mais pas un diviseur de 20). Il existe une méthode simple et systématique pour trouver GCD, appelée "algorithme d'Euclide". Cet article va vous montrer comment trouver le plus grand diviseur commun de deux entiers.

Pas

Méthode 1 sur 2: Algorithme de diviseur

1. 1 Omettez tout signe moins.
2. 2 Apprenez la terminologie : en divisant 32 par 5,
   • 32 - dividende
   • 5 - diviseur
   • 6 - privé
   • 2 - reste
3. 3 Déterminez le plus grand des nombres. Il sera divisible et le plus petit nombre sera le diviseur.
4. 4 Écrivez l'algorithme suivant : (dividende) = (diviseur) * (quotient) + (reste)
5. 5 Mettez un plus grand nombre à la place du dividende et un plus petit nombre à la place du diviseur.
6. 6 Trouvez combien de fois le plus grand nombre est divisé par le plus petit et écrivez le résultat au lieu du quotient.
7. 7 Trouvez le reste et écrivez-le à la position appropriée dans l'algorithme.
8. 8 Écrivez à nouveau l'algorithme, mais (A) écrivez le diviseur précédent en tant que nouveau dividende et (B) le reste précédent en tant que nouveau diviseur.
9. 9 Répétez l'étape précédente jusqu'à ce que le reste soit 0.
10. 10 Le dernier diviseur sera le plus grand diviseur commun (PGC).
11. 11 Par exemple, trouvons le PGCD pour 108 et 30 :
12. 12 Remarquez comment les nombres 30 et 18 de la première ligne forment la deuxième ligne. Ensuite, 18 et 12 forment la troisième rangée, et 12 et 6 forment la quatrième rangée. Les multiples de 3, 1, 1 et 2 ne sont pas utilisés. Ils représentent le nombre de fois où le dividende est divisible par le diviseur et sont donc uniques à chaque ligne.

Méthode 2 sur 2: Facteurs premiers

1. 1 Omettez tout signe moins.
2. 2 Trouver les facteurs premiers des nombres. Présentez-les comme indiqué sur l'image.
   • Par exemple, pour 24 et 18 :
     • 24- 2x2x2x3
     • 18- 2x3x3
   • Par exemple, pour 50 et 35 :
     • 50- 2x5x5
     • 35- 5 x 7
3. 3 Trouvez des facteurs premiers communs.
   • Par exemple, pour 24 et 18 :
     • 24- 2 x 2 x 2 x 3
     • 18- 2 X 3 x 3
   • Par exemple, pour 50 et 35 :
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Multipliez les facteurs premiers communs.
   • Pour 24 et 18, multipliez 2 et 3 et obtenir 6... 6 est le plus grand dénominateur commun de 24 et 18.
   • Il n'y a rien à multiplier pour 50 et 35. 5 Est le seul facteur premier commun, et c'est le PGCD.
5. 5 Fait!

Conseils

• Une façon d'écrire ceci est : dividende> mod diviseur> = reste ; PGCD (a, b) = b si mod b = 0, et PGCD (a, b) = PGCD (b, a mod b) sinon.
• A titre d'exemple, trouvons le PGCD (-77,91). Tout d'abord, utilisez 77 au lieu de -77 : GCD (-77,91) se convertit en GCD (77,91). 77 est inférieur à 91, nous devons donc les échanger, mais réfléchissez au fonctionnement de l'algorithme si nous ne le faisons pas. En calculant 77 mod 91, on obtient 77 (77 = 91 x 0 + 77). Comme ce n'est pas zéro, nous considérons la situation (b, a mod b), c'est-à-dire PGCD (77,91) = PGCD (91,77). 91 mod 77 = 14 (14 est le reste). Ce n'est pas zéro, donc PGCD (91,77) devient PGCD (77,14). 77 mod 14 = 7. Ce n'est pas zéro, donc PGCD (77,14) devient PGCD (14,7). 14 mod 7 = 0 (puisque 14/7 = 2 sans reste). Réponse : PGCD (-77,91) = 7.
• La méthode décrite est très utile pour simplifier les fractions. Dans l'exemple ci-dessus : -77/91 = -11/13, puisque 7 est le plus grand dénominateur commun de -77 et 91.
• Si a et b sont égaux à zéro, alors tout nombre différent de zéro est leur diviseur, donc dans ce cas il n'y a pas de PGCD (les mathématiciens croient simplement que le plus grand diviseur commun de 0 et 0 est 0).