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

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

## Преглед
Најголемиот заеднички делител на броевите *a* и *b* се означува како НЗД(*a*,&nbsp;*b*), или понекогаш поедноставно како (*a*,&nbsp;*b*). На пример, НЗД(12, 18)&nbsp;=&nbsp;6, НЗД(-4,&nbsp;14)&nbsp;=&nbsp;2 и НЗД(5, 0)&nbsp;=&nbsp;5. Два броја се *заемно прости* ако нивниот најголем заеднички делител е еднаков на 1. На пример, 9 и 28 се прости.

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

: {42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}

## Пресметување
Најголемиот заеднички делител начелно може да се пресмета со множење на два броја и споредување на множителите, како во следниот пример: за да се најде НЗД(18, 84), ги наоѓаме простите множители од 18&nbsp;=&nbsp;2·3 2 и 84&nbsp;=&nbsp;2 2 ·3·7 и забележуваме дека *преклопувањето на* двата израза е 2·3; па НЗД(18, 84)&nbsp;=&nbsp;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*1 и *a*2 се заемно прости, тогаш нзд(*a*1·*a*2, *b*) = нзд(*a*1, *b*)·нзд(*a*2, *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 \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.

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

## Надворешни врски
* Имплементација на НЗД во јазикот ++
* Онлајн калкулатор
* Онлајн nzd калкулатор
* НЗД на

Категорија:Аритметички функции
Категорија:Елементарна аритметика