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

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

Преглед

Највећи заједнички делилац бројева и се означава као нзд, или некад једноставније као . На пример, нзд(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 нзд.

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

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

Својства

• Сваки заједнички делилац бројева и дели нзд.

• нзд, где и нису оба једнака нули се може дефинисати алтернативно и еквивалентно као најмањи позитиван цео број , који се може записати у облику где су и цели бројеви. Овај израз се назива Безуов идентитет. Бројеви и се могу добити коришћењем проширеног Еуклидовог алгоритма.

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

• Ако дели производ , и нзд, онда дели .

• Ако је било који цео број, онда нзд(·нзд() и нзд(нзд( Ако је различито од нуле, и заједнички је делилац бројева и , онда нзднзд.

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

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

• нзд је у блиској вези са најмањим заједничким садржаоцем нзс: имамо

нзд·нзс.

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

нзд(, нзс(, )) = нзс(нзд(, ), нзд(, ))

нзс(, нзд(, )) = нзд(нзс(, ), нзс(, )).

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

Вероватноћа да два случајно изабрана цела броја ${\displaystyle A}$ и ${\displaystyle B}$ имају дати највећи заједнички делилац ${\displaystyle d}$ је ${\displaystyle 6 \over {\pi ^{2}d^{2}}}$. Ово следи из карактеризације нзд() као целог броја ${\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.

Види још

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

Литература

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

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