Najveći zajednički delilac

Iz Vikipedije, slobodne enciklopedije
(preusmereno sa НЗД)
Skoči na: navigacija, pretraga

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,

{42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}

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:

\operatorname{nzd}(a,b)=\frac{a\cdot b}{\operatorname{nzs}(a,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 A i B imaju dati najveći zajednički delilac d je 6\over {\pi^2 d^2}. Ovo sledi iz karakterizacije nzd(A, B) kao celog broja d takvog da d|A,B i A/d i B/d su uzajamno prosti. Verovatnoća da dva cela broja dele faktor d je d^{-2}. Verovatnoća da su dva cela broja uzajamno prosta je 1/\zeta(2)=6/\pi^2.

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

\mathrm{E}(\mathrm{nzd}) = \sum_{d=2}^{\infty} d \frac{6}{\pi^2 d^2} = \frac{6}{\pi^2} \sum_{d=2}^{\infty} \frac{1}{d}

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 k \ge 3, očekivana vrednost je dobro definisana, i jednaka je

 \mathrm{E}(\mathrm{nzd} (X_1, \cdots, X_k)) = \sum_{d=2}^{\infty} d^{1-k} \zeta(k)^{-1} = \frac{\zeta(k-1)}{\zeta(k)} .

Za k=3, ovo je približno jednako 1,3684. Za k=4, 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]