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

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

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

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



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



 Својства 
 Секој заеднички делител на броевите 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. 
 НЗД е мултипликативна функција во следнава смисла: ако a1 и a2 се заемно прости, тогаш нзд(a1·a2, b) = нзд(a1, b)·нзд(a2, 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)).

 Веројатности и очекувана вредност 
Веројатноста дека два случајно избрани цели броеви  и  имаат даден најголем заеднички делител  е . Ова произлегува од карактеризацијата на nzd() како цел број  такво да  и  и  се меѓусебно прости. Веројатноста дека два цели броеви делат фактор  е . Веројатноста два цели броја да се заемно прости е .

Користејќи ги овие податоци, може да се пресмета очекуваната вредност на функцијата НЗД. Тоа е:



Последната сума е хармониски ред, кој дивергира. Затоа, очекуваната вредност на најголемиот заеднички делител на две променливи не е добро дефинирана. Сепак, ова не е секогаш точно. За најголем заеднички делител на променливи , очекуваната вредност е добро дефинирана и е еднаква на:

 .

За , ова е приближно еднакво на 1,3684. За , е приближно 1,1106.

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

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

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