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

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

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

Преглед[уреди | уреди извор]

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

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

Рачунање[уреди | уреди извор]

Највећи заједнички делилац се начелно може израчунати разлагањем два броја на просте чиниоце, и упоређивањем чинилаца, као у следећем примеру: да бисмо нашли нзд(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:

Својства[уреди | уреди извор]

  • Сваки заједнички делилац бројева 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) као целог броја таквог да и и су узајамно прости. Вероватноћа да два цела броја деле фактор је . Вероватноћа да су два цела броја узајамно проста је .

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

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

.

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

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