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

Из Википедије, слободне енциклопедије

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

Преглед[уреди]

Највећи заједнички делилац бројева a и b се означава као нзд(ab), или некад једноставније као (ab). На пример, нзд(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·32 и 84 = 22·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·am·b) = m·нзд(ab) и нзд(a + m·bb) = нзд(ab). Ако је m различито од нуле, и заједнички је делилац бројева a и b, онда нзд(a/mb/m) = нзд(ab)/m.
  • НЗД три броја се може рачунати као нзд(abc) = нзд(нзд(ab), c) = нзд(a, нзд(bc)). Стога кажемо да је НЗД асоцијативна операција.
нзд(ab)·нзс(ab) = a·b.
Ова формула се често користи за рачунање најмањег заједничког садржаоца: прво се НЗД израчуна помоћу Еуклидовог алгоритма, а затим се производ два броја подели њиховим НЗД. Следеће верзије дистрибутивности важе:
нзд(a, нзс(bc)) = нзс(нзд(ab), нзд(ac))
нзс(a, нзд(bc)) = нзд(нзс(ab), нзс(ac)).

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

Вероватноћа да два случајно изабрана цела броја 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 \ge 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 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."

Спољашње везе[уреди]