Најголем заеднички делител

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

Преглед

Најголемиот заеднички делител на броевите 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 не се еднакви на нула може да се дефинира алтернативно и еквивалентно како најмал позитивен цел број d, кој може да се напише во облик d = a·p + b·q каде p и q се цели броеви. Овој израз се нарекува Безуов идентитет. Броевите a и b може да се добијат со помош на проширениот Евклидов алгоритам.
• НЗД(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, c)) = нзс(нзд(a, b), нзд(a, c))

нзс(a, нзд(b, c)) = нзд(нзс(a, b), нзс(a, c)).

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

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

Поврзано

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

Надворешни врски

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