collapse
Skupovi: N, Z, Q, I i R (klikni za pregled sadrzaja):
[close]

Tema: (1) Najveci zajednicki delilac brojeva - NZD i Euklidov algoritam  (Pročitano 8975 puta)

  • [applaud]0
  • [smite]0

  • Druga metoda za trazenje NZD-a je metoda razlaganja brojeva na proste cinioce
    i  objasnjena je u narednoj temi.



    Teorema 2.  Euklidov algoritam:

    Ako su a i b celi brojevi, pri cemu je a>b>0 i b nije delilac broja a, tada postoji prirodni broj n i celi brojevi q1, q2, q3, ..., qn, r1, r2,r3, ..., rn takvi da je:




    NZD(a,b) = r_{n}



    NZD dva broja je najveći broj koji istovremeno deli oba bez ostatka.

    Primer: Pronaci NZD(18,84)

    84/18 = 4  sa ostatkom 12
    18/12 = 1 sa ostatkom 6
    12/6 = 2 sa ostatkom nula   \Rightarrow  NZD(18,84) = 6.


    Euklidov algoritam je zasnovan na principu da se najveći zajednički delilac dva broja ne menja ukoliko se manji broj oduzme od većeg, pa se zatim odredi NZD novodobijenog broja i manjeg od prethodna dva.

    Na primer, 21 je NZD za 252 i 105 (252 = 21 × 12; 105 = 21 × 5); pošto je 252 − 105 = 147, NZD za 147 i 105 je takođe 21.

    Kako je veći od dva polazna broja na ovaj način smanjen, ponavljanjem postupka dobijaće se sve manji brojevi, dok se jedan od njih ne svede na nulu.
    U tom trenutku, drugi broj je jednak najvećem zajedničkom deliocu dva polazna broja.

    Ukoliko se obrne redosled koraka u Euklidovom algoritmu, NZD se moze izraziti kao zbir dva polazna broja od kojih je svaki pomnožen nekim celim brojem, u prethodnom primeru je 21 = 5 × 105 + (−2) × 252.

    Ova vazna osobina je poznata kao Bezuov identitet.


       « Poslednja izmena: 28. 09. 2016. | 11:40:09 Matematika »