Највећи заједнички делилац

У математици, највећи заједнички делилац (НЗД) два цела броја различита од нуле је највећи позитиван цео број који дели оба броја без остатка.

Преглед

Највећи заједнички делилац бројева -{a}- и -{b}- се означава као нзд-{(a, b)}-, или некад једноставније као -{(a, b)}-. На пример, нзд(12, 18) = 6, нзд(−4, 14) = 2 и нзд(5, 0) = 5. Два броја су узајамно проста ако им је највећи заједнички делилац једнак 1. На пример, 9 и 28 су узајамно прости.

Највећи заједнички делилац је користан за скраћивање разломака. На пример, нзд(42, 56)=14, стога,

$\frac{42}{56}=\frac{3\cdot 14}{4\cdot 14}=\frac{3}{4}$

Рачунање

Највећи заједнички делилац се начелно може израчунати разлагањем два броја на просте чиниоце, и упоређивањем чинилаца, као у следећем примеру: да бисмо нашли нзд(18, 84), налазимо просте чиниоце од 18 = 2·3² и 84 = 2²·3·7 и примећујемо да је преклапање два израза 2·3; па је нзд(18, 84) = 6. У пракси, овај метод је изводљив само за јако мале бројеве; разлагање на просте чиниоце начелно може да буде врло компликовано.

Много ефикаснији метод је Еуклидов алгоритам, који користи алгоритам за дељење у комбинацији са чињеницом да нзд два броја такође дели и њихову разлику: поделимо 84 са 18 и добијемо количник 4 и остатак 12. Затим поделимо 18 са 12 и добијемо количник 1 и остатак 6. Затим поделимо 12 са 6 и добијемо остатак 0, што значи да је 6 нзд.

Ако -{a}- и -{b}- нису оба једнака нули, највећи заједнички делилац -{a}- и -{b}- се може израчунати коришћењем најмањег заједничког садржаоца (нзс) бројева -{a}- и -{b}-:

$\mathrm{nzd}(a,b)=\frac{a\cdot b}{\mathrm{nzs}(a,b)}.$

Својства

• Сваки заједнички делилац бројева -{a}- и -{b}- дели нзд-{(a, b)}-.

• нзд-{(a, b)}-, где -{a}- и -{b}- нису оба једнака нули се може дефинисати алтернативно и еквивалентно као најмањи позитиван цео број -{d}-, који се може записати у облику -{d = a·p + b·q}- где су -{p}- и -{q}- цели бројеви. Овај израз се назива Безуов идентитет. Бројеви -{p}- и -{q}- се могу добити коришћењем проширеног Еуклидовог алгоритма.

• нзд(-{a}-, 0) = |-{a}-|, за -{a}- ≠ 0, јер сваки број дели 0, а највећи делилац -{a}- је |-{a}-|. Ово се обично користи као основни случај Еуклидовог алгоритма.

• Ако -{a}- дели производ -{b·c}-, и нзд-{(a, b) = d}-, онда -{a/d}- дели -{c}-.

• Ако је -{m}- било који цео број, онда нзд(-{m·a, m·b) = m}-·нзд(-{a, b}-) и нзд(-{a + m·b, b) = }-нзд(-{a, b).}- Ако је -{m}- различито од нуле, и заједнички је делилац бројева -{a}- и -{b}-, онда нзд-{(a/m, b/m) = }-нзд-{(a, b)/m}-.

• НЗД је мултипликативна функција у следећем смислу: ако су -{a}-₁ и -{a}-₂ узајамно прости, тада нзд(-{a}-₁·-{a}-₂, -{b}-) = нзд-{(a₁, b)}-·нзд-{(a₂, b)}-.

• НЗД три броја се може рачунати као нзд-{(a, b, c)}- = нзд(нзд(-{a, b), c)}- = нзд(-{a}-, нзд-{(b, c))}-. Стога кажемо да је НЗД асоцијативна операција.

• нзд-{(a, b)}- је у блиској вези са најмањим заједничким садржаоцем нзс-{(a, b)}-: имамо

нзд-{(a, b)}-·нзс-{(a, b) = a·b}-.

Ова формула се често користи за рачунање најмањег заједничког садржаоца: прво се НЗД израчуна помоћу Еуклидовог алгоритма, а затим се производ два броја подели њиховим НЗД. Следеће верзије дистрибутивности важе:

нзд(-{a}-, нзс(-{b}-, -{c}-)) = нзс(нзд(-{a}-, -{b}-), нзд(-{a}-, -{c}-))

нзс(-{a}-, нзд(-{b}-, -{c}-)) = нзд(нзс(-{a}-, -{b}-), нзс(-{a}-, -{c}-)).

Вероватноће и очекивана вредност

Вероватноћа да два случајно изабрана цела броја $A$ и $B$ имају дати највећи заједнички делилац $d$ је $\frac{6}{{\pi }^2{d}^2}$. Ово следи из карактеризације нзд(-{A, B}-) као целог броја $d$ таквог да $d|A,B$ и $A/d$ и $B/d$ су узајамно прости. Вероватноћа да два цела броја деле фактор $d$ је $d^{-2}$. Вероватноћа да су два цела броја узајамно проста је $1/\zeta (2)=6/{\pi }^2$.

Коришћењем ових података, може се израчунати очекивана вредност функције НЗД. То је

$\mathrm{E}(\mathrm{n}\mathrm{z}\mathrm{d})=\sum _{d=2}^{\mathrm{\infty }}d\frac{6}{{\pi }^2{d}^2}=\frac{6}{{\pi }^2}\sum _{d=2}^{\mathrm{\infty }}\frac{1}{d}$

Задња сума је хармонијски ред, који дивергира. Стога очекивана вредност највећег заједничког делиоца два променљиве није добро дефинисана. Ово међутим није увек тачно. За највећи заједнички делилац променљивих $k\ge 3$, очекивана вредност је добро дефинисана, и једнака је

$\mathrm{E}(\mathrm{n}\mathrm{z}\mathrm{d}(X_1,\cdots ,X_k))=\sum _{d=2}^{\mathrm{\infty }}{d}^{1-k}\zeta (k{)}^{-1}=\frac{\zeta (k-1)}{\zeta (k)}$.

За $k=3$, ово је приближно једнако 1,3684. За $k=4$, је приближно 1,1106.

Види још

• Најмањи заједнички садржалац
• Проширени Еуклидов алгоритам

Литература

• -{Шаблон:Cite book, Third Edition. Addison-Wesley. . Section 4.5.2: The Greatest Common Divisor, pp. 333-356.}-
• -{Шаблон:Cite book, Second Edition. MIT Press and McGraw-Hill. . Section 31.2: Greatest common divisor, pp. 856-862.}-
• -{Шаблон:Cite book

Спољашње везе

• НЗД имплементација у језику -{C}-++
• Онлајн калкулатор
• Онлајн нзд калкулатор
• НЗД на -{Everything2.com}-