Cel mai mare divizor comun

anterior ◈ următoarea

Găsirea GCD folosind factorizarea

Cel mai mare număr natural prin care numărul de împărțit fără rest și b, numit cel mai mare comună divizor al numerelor. Notăm GCD (a, b).







Luați în considerare exemplul de a găsi GCD a două numere întregi 18 și 60:

  • 1 Noi extinde numărul de numere prime:
    18 = 2 x 3 x 3
    60 = 2 x 2 x 3 x 5
  • 2 lovit din prima expansiune a tuturor factorilor care nu sunt incluse în extinderea celui de al doilea număr, se obține un 2 x 3 x 3.
  • 3 înmulțiri Primes rămase după ștergere și de a obține cel mai mare divizor comun al numerelor: (. 18 60) GCD = 2 x 3 = 6.
  • 4 Rețineți că nu este important din prima sau a doua a multiplicatorilor strabat, rezultatul este același:
    18 = 2 x 3 x 3
    60 = 2 x 2 x 3 x 5
Exemplu Găsiți cmmdc de 111 și 324. 432

Șters din primul număr, factori care nu sunt prezente în al doilea și al treilea număr, se obține:

Găsirea GCD folosind algoritmul lui Euclid

O a doua metodă pentru a găsi cel mai mare divizor comun, folosind algoritmul lui Euclid. Algoritmul lui Euclid este cel mai eficient mod de a găsi GCD. utilizarea este necesar să se găsească în mod constant restul împărțirii numerelor și se aplică formula de recurență.







Formula recurență pentru GCD, cmmdc (a, b) = cmmdc (b, a b mod). în cazul în care un mod b - restul de divizare pe b.

Algoritmul lui Euclid
Exemplul Găsiți cel mai mare divizor comun al 7920 și 594

Găsim GCD (7920. 594) folosind algoritmul euclidian, pentru a calcula restul de divizare va fi folosind calculatorul.

GCD rezultat (7920. 594) = 198

Găsirea cel mai mic multiplu comun

Găsirea NOC prin factorizarea

Cel mai mic multiplu comun al numerelor naturale a și b este cel mai mic număr natural. este un multiplu de și, și b. LCM Notată (a, b).

Luați în considerare exemplul de a găsi LCM două numere naturale 18 și 60:

  • 1 Noi extinde numărul de numere prime:
    18 = 2 x 3 x 3
    60 = 2 x 2 x 3 x 5
  • 2 Adăugarea factorilor care lipsesc din descompunerea al doilea număr, obținem un 2 x 2 x 3 x 3 x 5.
  • 3 multiplică factorii principali după adăugare și de a obține cel mai mic multiplu comun al numerelor: (. 18 60) LCM = 2 x 2 x 3 x 3 x 5 = 180.
EXEMPLUL Găsiți cel mai mic multiplu comun al numerelor 168, 231 și 60

Adăugarea numărului primelor multiplicatorilor de-al doilea și al treilea număr, obținem:

2 x 2 x 2 x 3 x 5 x 11 x 7 = 9240.

Găsirea cel mai mic multiplu comun prin utilizarea cmmdc

Dacă GCD a numerelor este cunoscută, NOC poate fi calculat prin formula

EXEMPLU Găsiți cel mai mic multiplu comun al numerelor 54 și 72, dacă cmmdc (54, 72) = 18.

Folosind formula constatare NOC prin GCD obține







anterior ◈ următoarea