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

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

== Преглед ==
Најголемиот заеднички делител на броевите ''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, затоа,

: <math>{42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}</math>

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

: <math>\operatorname{nzd}(a,b)=\frac{a\cdot b}{\operatorname{nzs}(a,b)}.</math>

== Својства ==
* Секој заеднички делител на броевите ''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''<sub>1</sub> и ''a''<sub>2</sub> се заемно прости, тогаш нзд(''a''<sub>1</sub>·''a''<sub>2</sub>, ''b'') = нзд(''a''<sub>1</sub>, ''b'')·нзд(''a''<sub>2</sub>, ''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'')).

== Веројатности и очекувана вредност ==
[[Веројатност|Веројатноста]] дека два случајно избрани цели броеви <math>A</math> и <math>B</math> имаат даден најголем заеднички делител <math>d</math> е <math>6\over {\pi^2 d^2}</math>. Ова произлегува од карактеризацијата на nzd() како цел број <math>d</math> такво да <math>d|A,B</math> и <math>A/d</math> и <math>B/d</math> се меѓусебно прости. Веројатноста дека два цели броеви делат фактор <math>d</math> е <math>d^{-2}</math>. Веројатноста два цели броја да се заемно прости е <math>1/\zeta(2)=6/\pi^2</math>.

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

: <math>\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}</math>

Последната сума е [[хармониски ред]], кој дивергира. Затоа, очекуваната вредност на најголемиот заеднички делител на две променливи не е добро дефинирана. Сепак, ова не е секогаш точно. За најголем заеднички делител на променливи <math>k \ge 3</math>, очекуваната вредност е добро дефинирана и е еднаква на:

: <math> \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)} </math>.

За <math>k=3</math>, ова е приближно еднакво на 1,3684. За <math>k=4</math>, е приближно 1,1106.

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

== Надворешни врски ==
* [http://www.tekpool.com/?p=56 Имплементација на НЗД во јазикот ++]
* [http://www.easycalculation.com/hcf.php Онлајн калкулатор]
* [http://wims.unice.fr/wims/wims.cgi?module=tool/popup.en&search=gcd Онлајн nzd калкулатор]
* [http://everything2.com/?node_id=482506 НЗД на]

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