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

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

Преглед

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

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

{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:

\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)).

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

Вероватноћа да два случајно изабрана цела броја $A$ и $B$ имају дати највећи заједнички делилац $d$ је $6 \over {\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 {nzd} )=\sum _{d=2}^{\infty }d{\frac {6}{\pi ^{2}d^{2}}}={\frac {6}{\pi ^{2}}}\sum _{d=2}^{\infty }{\frac {1}{d}}

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

\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)}}

.

За $k=3$ , ово је приближно једнако 1,3684. За $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."