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

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

Преглед

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

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

${\displaystyle {42 \over 56}={3\cdot 14 \over 4\cdot 14}={3 \over 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:

${\displaystyle \operatorname {nzd} (a,b)={\frac {a\cdot b}{\operatorname {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)).

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

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

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

${\displaystyle \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}}}$

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

${\displaystyle \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)}}}$.

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

Види још

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

Литература

• 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."

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

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