Najveći zajednički delilac

Iz Vikipedije, slobodne enciklopedije
(preusmereno sa НЗД)
Idi na: navigaciju, pretragu

U matematici, najveći zajednički delilac (NZD) dva cela broja različita od nule je najveći pozitivan ceo broj koji deli oba broja bez ostatka.

Pregled[uredi]

Najveći zajednički delilac brojeva a i b se označava kao nzd(ab), ili nekad jednostavnije kao (ab). Na primer, nzd(12, 18) = 6, nzd(−4, 14) = 2 i nzd(5, 0) = 5. Dva broja su uzajamno prosta ako im je najveći zajednički delilac jednak 1. Na primer, 9 i 28 su uzajamno prosti.

Najveći zajednički delilac je koristan za skraćivanje razlomaka. Na primer, nzd(42, 56)=14, stoga,

Računanje[uredi]

Najveći zajednički delilac se načelno može izračunati razlaganjem dva broja na proste činioce, i upoređivanjem činilaca, kao u sledećem primeru: da bismo našli nzd(18, 84), nalazimo proste činioce od 18 = 2·32 i 84 = 22·3·7 i primećujemo da je preklapanje dva izraza 2·3; pa je nzd(18, 84) = 6. U praksi, ovaj metod je izvodljiv samo za jako male brojeve; razlaganje na proste činioce načelno može da bude vrlo komplikovano.

Mnogo efikasniji metod je Euklidov algoritam, koji koristi algoritam za deljenje u kombinaciji sa činjenicom da nzd dva broja takođe deli i njihovu razliku: podelimo 84 sa 18 i dobijemo količnik 4 i ostatak 12. Zatim podelimo 18 sa 12 i dobijemo količnik 1 i ostatak 6. Zatim podelimo 12 sa 6 i dobijemo ostatak 0, što znači da je 6 nzd.

Ako a i b nisu oba jednaka nuli, najveći zajednički delilac a i b se može izračunati korišćenjem najmanjeg zajedničkog sadržaoca (nzs) brojeva a i b:

Svojstva[uredi]

  • Svaki zajednički delilac brojeva a i b deli nzd(a, b).
  • nzd(a, b), gde a i b nisu oba jednaka nuli se može definisati alternativno i ekvivalentno kao najmanji pozitivan ceo broj d, koji se može zapisati u obliku d = a·p + b·q gde su p i q celi brojevi. Ovaj izraz se naziva Bezuov identitet. Brojevi p i q se mogu dobiti korišćenjem proširenog Euklidovog algoritma.
  • nzd(a, 0) = |a|, za a ≠ 0, jer svaki broj deli 0, a najveći delilac a je |a|. Ovo se obično koristi kao osnovni slučaj Euklidovog algoritma.
  • Ako a deli proizvod b·c, i nzd(a, b) = d, onda a/d deli c.
  • Ako je m bilo koji ceo broj, onda nzd(m·am·b) = m·nzd(ab) i nzd(a + m·bb) = nzd(ab). Ako je m različito od nule, i zajednički je delilac brojeva a i b, onda nzd(a/mb/m) = nzd(ab)/m.
  • NZD je multiplikativna funkcija u sledećem smislu: ako su a1 i a2 uzajamno prosti, tada nzd(a1·a2b) = nzd(a1b)·nzd(a2b).
  • NZD tri broja se može računati kao nzd(abc) = nzd(nzd(ab), c) = nzd(a, nzd(bc)). Stoga kažemo da je NZD asocijativna operacija.
nzd(ab)·nzs(ab) = a·b.
Ova formula se često koristi za računanje najmanjeg zajedničkog sadržaoca: prvo se NZD izračuna pomoću Euklidovog algoritma, a zatim se proizvod dva broja podeli njihovim NZD. Sledeće verzije distributivnosti važe:
nzd(a, nzs(bc)) = nzs(nzd(ab), nzd(ac))
nzs(a, nzd(bc)) = nzd(nzs(ab), nzs(ac)).

Verovatnoće i očekivana vrednost[uredi]

Verovatnoća da dva slučajno izabrana cela broja i imaju dati najveći zajednički delilac je . Ovo sledi iz karakterizacije nzd(A, B) kao celog broja takvog da i i su uzajamno prosti. Verovatnoća da dva cela broja dele faktor je . Verovatnoća da su dva cela broja uzajamno prosta je .

Korišćenjem ovih podataka, može se izračunati očekivana vrednost funkcije NZD. To je

Zadnja suma je harmonijski red, koji divergira. Stoga očekivana vrednost najvećeg zajedničkog delioca dva promenljive nije dobro definisana. Ovo međutim nije uvek tačno. Za najveći zajednički delilac promenljivih , očekivana vrednost je dobro definisana, i jednaka je

.

Za , ovo je približno jednako 1,3684. Za , je približno 1,1106.

Vidi još[uredi]

Literatura[uredi]

  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp.333-356.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp.856-862.
  • Saunders MacLane and Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1-7: "The Euclidean Algorithm."

Spoljašnje veze[uredi]