Najveći zajednički delilac

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(a, b), ili nekad jednostavnije kao (a, b). 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·3² i 84 = 2²·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·a, m·b) = m·nzd(a, b) i nzd(a + m·b, b) = nzd(a, b). Ako je m različito od nule, i zajednički je delilac brojeva a i b, onda nzd(a/m, b/m) = nzd(a, b)/m.

NZD je multiplikativna funkcija u sledećem smislu: ako su a₁ i a₂ uzajamno prosti, tada nzd(a₁·a₂, b) = nzd(a₁, b)·nzd(a₂, b).

NZD tri broja se može računati kao nzd(a, b, c) = nzd(nzd(a, b), c) = nzd(a, nzd(b, c)). Stoga kažemo da je NZD asocijativna operacija.

nzd(a, b) je u bliskoj vezi sa najmanjim zajedničkim sadržaocem nzs(a, b): imamo

nzd(a, b)·nzs(a, b) = 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(b, c)) = nzs(nzd(a, b), nzd(a, c))

nzs(a, nzd(b, c)) = nzd(nzs(a, b), nzs(a, c)).

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\geq 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 978-0-201-89684-8.. 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 978-0-262-03293-3.. 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 978-0-02-310070-3.. 1-7: "The Euclidean Algorithm."