DifiTsi.com

Aflați cel mai mare divizor comun de două numere întregi


Cel mai mare divizor comun (gcd) a două numere întregi este cel mai mare întreg care poate servi drept divizor pentru ambele numere. De exemplu, cel mai mare număr care poate diviza ambele 20 și 16 este 4. (Ambele 16 și 20 au divizori mai mari, dar nu mai mari comun

Dividerul - 8 este de ex. un divizor de 16, dar nu 20)

În școala primară, copiii sunt de obicei învățați că pot găsi gcd prin "încercarea și verificarea". Dar există și o modalitate simplă și sistematică de a obține rezultatul corect. Această metodă se numește "Algoritmul euclidian".

metodă

Metoda 1
1

Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 1
1
Îndepărtați toate semnele negative.
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 2
    2
    Cunoașteți expresiile matematice: Dacă împărțiți 32 cu 5, atunci este
  • 32 dividendul
  • 5 divizorul
  • 6 coeficientul
  • 2 restul (sau modulo).
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 3
    3
    Determinați cele mai mari dintre cele două numere. Acesta va fi dividendul și cu atât divizorul va fi mai mic.
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 4
    4
    Notați algoritmul: (Dividend) = (divizor) * (coeficientul) + (restul)
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 5
    5
    Puneți numărul mai mare în locul dividendului și cel mai mic în locul divizorului.
  • Imaginea intitulată Găsiți cel mai mare divizor al celor două numere întregi Pasul 6
    6
    Determinați cât de des se potrivește numărul mai mic în cel mai mare și scrieți rezultatul în locul coeficientului.
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 7
    7
    Calculați suma rămasă și scrieți-o în locul corespunzător din algoritm.
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a celor două numere întregi Pasul 8
    8
    Notați algoritmul cu valorile încă o dată, dar de această dată utilizați A) divizorul vechi ca nou dividend și B) restul ca noul divizor.
  • Imaginea intitulată Găsiți cel mai mare divizor al celor două numere întregi Pasul 9
    9
    Repetați pasul anterior până când restul este zero.


  • Imaginea intitulată Găsiți cel mai mare divizor al celor două numere întregi Pasul 10
    10
    Ultimul divizor primit este cel mai mare divizor comun.
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 11
    11
    Iată un exemplu în care încercăm să găsim gcd-ul de 108 și 30:
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 12
    12
    Observați modul în care pozițiile 30 și 18 ale primelor linii de swap pentru a crea a doua linie. După aceea, 18 și 12 sunt schimbate pentru a genera de-a treia linie și în mod similar, 12 și schimbat 6 pentru a genera a patra linie. Valorile 3, 1, 1 și 2, care sunt scrise după semnul de multiplicare, nu se arunca cu capul din nou. Acestea reprezintă cât de des divizorul se încadrează în dividende și, prin urmare, este unic pentru fiecare linie.

    • Metoda 2
    2

    Imaginea intitulată Găsiți cea mai mare divizoare comună a două numere întregi Pasul 13
    1
    Îndepărtați toate semnele negative.
  • Imaginea intitulată Găsiți cel mai mare divizor al celor două numere întregi Pasul 14
    2
    Împărțiți fiecare număr în principalii ei factori și scrieți-i în jos, după cum se arată în exemplul următor.
  • Numerele pentru exemplul 1 sunt 24 și 18:
  • 24 = 2 x 2 x 2 x 3
  • 18 = 2 x 3 x 3
  • Numerele pentru exemplul nostru 2 sunt de 50 și 35:
  • 50 = 2 x 5 x 5
  • 35 = 5x7
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a celor două numere întregi Pasul 15
    3
    Determinați toți factorii principali primari.
  • În Exemplul 1:
  • 24 = 2 x 2 x 2 x 3
  • 18 = 2 x 3 x 3
  • În exemplul 2:
  • 50 = 2 x 5 x 5
  • 35 = 5 x 7
  • 4
    Înmulțiți factorii principali primi unul cu celălalt.
  • În Exemplul 1, înmulțiți cei doi factori primari 2 și 3, primiți 6. Asta este 6 cel mai mare divizor comun de 24 și 18 ani.
  • În exemplul 2, nu puteți multiplica nimic între ele. 5 este singurul divizor comun de 50 și 35 și astfel automat cel mai mare divizor comun.
  • Imaginea intitulată Găsiți cea mai mare divizoare comună a două intregi intro
    5
    Efectuat.

    • Sfaturi

    • O posibilă ortografie este folosirea notației mod = Remainder, unde rezultatul este gcd (a, b) = b, dacă un mod b = 0 și altfel gcd (a, b) = gcd (b, a mod b).
    • Să facem acest lucru folosind exemplul gcd (-77,91). În primul rând, folosim 77 în loc de -77, deci gcd (-77.91) devine gcd (77.91). Din moment ce 77 este mai mică de 91, ar trebui să schimbăm valorile. Dar să aruncăm o privire la felul în care se comportă algoritmul dacă nu facem acest lucru. Dacă calculăm 77 mod 91, obținem 77 (de la 77 = 91 x 0 + 77). Deoarece acest lucru nu este egal cu zero, schimbăm (a, b) cu (b, a mod b) și obținem: gcd (77,91) = gcd (91,77). 91 mod 77 dă 14 (rețineți că 14 este restul). Deoarece aceasta nu este egală cu zero, schimbăm gcd (91.77) cu gcd (77.14). 77 mod 14 returnează 7, care nu este egal cu zero. Schimbăm gcd (77,14) cu gcd (14,7). 14 mod 7 este aceeași Zero, din moment ce 14 = 7 * 2 fără rest, așa că ne oprim la acest punct. Și asta înseamnă: gcd (-77,91) = 7.
    • Această tehnică este foarte utilă pentru scurtarea fracturilor. Pentru a rămâne cu exemplul de mai sus, pauza -77/91 poate fi scurtat la -11/13, deoarece 7 este cel mai mare divizor comun al -77 și 91 de
    • Dacă "a" și "b" sunt ambele, atunci ambele numere pot fi împărțite cu orice număr care nu este zero, deci în acest caz nu există, de fapt, cel mai mare divizor comun. Matematicienii spun în acest caz că cel mai mare divizor comun în acest caz este, de asemenea, zero, și acesta este, de asemenea, rezultatul acestui algoritm.
    Distribuiți pe rețelele sociale:

    înrudit