Conţinut

• Pași
• Metoda 1 din 2: Algoritm divizor
• Metoda 2 din 2: Factori primi
• sfaturi

Cel mai mare divizor comun (GCD) din două numere întregi este cel mai mare întreg care împarte fiecare dintre aceste numere. De exemplu, mcd pentru 20 și 16 este 4 (ambii 16 și 20 au divizori mari, dar nu sunt comuni - de exemplu, 8 este divizorul lui 16, dar nu divizorul lui 20). Există o metodă simplă și sistematică pentru găsirea GCD, numită „algoritmul lui Euclid”. Acest articol vă va arăta cum să găsiți cel mai mare divizor comun al a două numere întregi.

Pași

Metoda 1 din 2: Algoritm divizor

1. 1 Omiteți orice semne minus.
2. 2 Aflați terminologia: atunci când se împarte 32 la 5,
   • 32 - dividend
   • 5 - divizor
   • 6 - privat
   • 2 - rest
3. 3 Determinați numărul mai mare. Va fi divizibil, iar numărul mai mic va fi divizorul.
4. 4 Notați următorul algoritm: (dividend) = (divizor) * (coeficient) + (rest)
5. 5 Puneți un număr mai mare în locul dividendului și un număr mai mic în locul divizorului.
6. 6 Găsiți de câte ori numărul mai mare este împărțit la cel mai mic și scrieți rezultatul în loc de coeficient.
7. 7 Găsiți restul și scrieți-l în poziția corespunzătoare din algoritm.
8. 8 Scrieți din nou algoritmul, dar (A) scrieți divizorul anterior ca un dividend nou și (B) restul anterior ca un nou divizor.
9. 9 Repetați pasul anterior până când restul este 0.
10. 10 Ultimul divizor va fi cel mai mare divizor comun (GCD).
11. 11 De exemplu, să găsim GCD pentru 108 și 30:
12. 12 Observați cum numerele 30 și 18 din prima linie formează a doua linie. Apoi 18 și 12 formează al treilea rând, iar 12 și 6 formează al patrulea rând. Nu se folosesc multipli de 3, 1, 1 și 2. Ele reprezintă de câte ori dividendul este divizibil cu divizorul și, prin urmare, sunt unice pentru fiecare rând.

Metoda 2 din 2: Factori primi

1. 1 Omiteți orice semne minus.
2. 2 Găsiți factorii primi ai numerelor. Prezentați-le așa cum se arată în imagine.
   • De exemplu, pentru 24 și 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • De exemplu, pentru 50 și 35:
     • 50- 2 x 5 x 5
     • 35-5 x 7
3. 3 Găsiți factori primi comuni.
   • De exemplu, pentru 24 și 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 X 3 x 3
   • De exemplu, pentru 50 și 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Înmulțiți factorii primi comuni.
   • Pentru 24 și 18, înmulțiți-vă 2 și 3 si ia 6... 6 este cel mai mare numitor comun al 24 și 18.
   • Nu este nimic de înmulțit pentru 50 și 35. 5 Este singurul factor prim comun și este GCD.
5. 5 Făcut!

sfaturi

• O modalitate de a scrie acest lucru este: dividend> mod divider> = rest; GCD (a, b) = b dacă mod b = 0 și gcd (a, b) = gcd (b, a mod b) în caz contrar.
• De exemplu, să găsim GCD (-77.91). În primul rând, utilizați 77 în loc de -77: GCD (-77.91) convertește în GCD (77.91). 77 este mai puțin de 91, deci trebuie să le schimbăm, dar ia în considerare modul în care funcționează algoritmul dacă nu. Când calculăm 77 mod 91, obținem 77 (77 = 91 x 0 + 77). Deoarece acest lucru nu este zero, considerăm situația (b, a mod b), adică GCD (77.91) = GCD (91.77). 91 mod 77 = 14 (14 este restul). Nu este zero, deci GCD (91.77) devine GCD (77.14). 77 mod 14 = 7. Acesta nu este zero, deci GCD (77.14) devine GCD (14.7). 14 mod 7 = 0 (din 14/7 = 2 fără rest). Răspuns: GCD (-77.91) = 7.
• Metoda descrisă este foarte utilă pentru simplificarea fracțiilor. În exemplul de mai sus: -77/91 = -11/13, deoarece 7 este cel mai mare numitor comun al lui -77 și 91.
• Dacă a și b sunt egale cu zero, atunci orice număr diferit de zero este divizorul lor, deci în acest caz nu există GCD (matematicienii cred pur și simplu că cel mai mare divizor comun al 0 și 0 este 0).