Найбольшы агульны дзельнік

**Найбольшы агу́льны дзе́льнік** (**НАД**) двух цэлых лікаў  і  — самы вялікі натуральны лік, які дзеліць і , і . Іншымі словамі, гэта самы вялікі з іх агульных дзельнікаў. Прыклад: для лікаў 70 і 105 найбольшы агульны дзельнік роўны 35.

Найбольшы агульны дзельнік існуе і вызначаны адназначна, калі хаця б адзін з лікаў  і  не нулявы.

Сустракаюцца наступныя абазначэнні найбольшага агульнага дзельніка  і :
* 
* 
*  (ад англ. *Greatest Common Divisor*)
*  (ад  *Highest Common Factor*)

Паняцце найбольшага агульнага дзельніка натуральным чынам абагульняецца на наборы з больш чым двух цэлых лікаў.

## Звязаныя азначэнні 
### Найменшае агульнае кратнае 
**Найменшае агульнае кратнае** (**НАК**) двух цэлых лікаў  і  — гэта найменшы натуральны лік, які дзеліцца і на , і на . Абазначаецца  ці , а ў англамоўнай літаратуры .

НАК ненулявых лікаў  і  заўсёды існуе і звязаны з НАД наступнымі суадносінамі:
: (m,n)\cdot[m,n]=m\cdot n.

Гэта асобны выпадак больш агульнай тэарэмы:
калі a_1, a_2, \dots , a_n — ненулявыя лікі, D — якое-небудзь іх агульнае кратнае, то справядліва формула:
: D = [a_1, a_2, \dots , a_n] \cdot \left(\frac{D}{a_1}, \frac{D}{a_2}, \dots , \frac{D}{a_n}\right).

### Узаемна простыя лікі 
Лікі  і  называюцца **ўзаемна-простымі**, калі ў іх няма агульных дзельнікаў, акрамя адзінкі. Для такіх лікаў . І наадварот, калі , то лікі ўзаемна простыя.

Падобным чынам, цэлыя лікі a_1, a_2, \dots a_k, дзе k\geq 2, называюцца **ўзаемна простымі**, калі іх найбольшы агульны дзельнік роўны адзінцы.

Трэба адрозніваць паняцці *ўзаемнай прастаты*, калі НАД набору лікаў роўны 1, і *папарнай узаемнай прастаты*, калі НАД ровен 1 для кожнай пары лікаў з набору. З папарнае прастаты вынікае ўзаемная прастата, але не наадварот. Напрыклад, НАД(6,10,15) = 1, але любыя пары з гэтага набору не ўзаемна простыя.

## Спосабы вылічэння 
НАД двух лікаў можна эфектыўна вылічыць па алгарытме Еўкліда і бінарным алгарытме.

Акрамя таго, значэнне  можна лёгка вылічыць, калі вядома кананічнае раскладанне лікаў  і  на простыя множнікі:
:: n=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},
:: m=p_1^{e_1}\cdot \dots \cdot p_k^{e_k},
дзе p_1,\dots,p_k — розныя простыя лікі, а d_1,\dots,d_k і e_1,\dots,e_k — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведны просты адсутнічае ў раскладанні). Тады  і  выражаюцца формуламі:
:: (n,m)=p_1^{\min(d_1,e_1)}\cdot\dots\cdot p_k^{\min(d_k,e_k)},
:: [n,m]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.

Калі лікаў больш чым два: a_1, a_2,\dots a_n, іх НАД шукаюць па наступным алгарытме:
: d_2=(a_1, a_2)
: d_3=(d_2, a_3)
:: ………
: d_n=(d_{n-1}, a_n) — гэта і ёсць шуканы НАД.

## Уласцівасці 
* Асноўная ўласцівасць: найбольшы агульны дзельнік  і  дзеліцца на любы агульны дзельнік гэтых лікаў. Прыклад: для лікаў 12 і 18 найбольшы агульны дзельнік ровен 6; ён дзеліцца на ўсе агульныя дзельнікі гэтых лікаў: 1, 2, 3, 6.
** Вынік 1: мноства агульных дзельнікаў  і  супадае з мноствам дзельнікаў .
** Вынік 2: мноства агульных кратных  і  супадае з мноствам кратных .
* Калі  дзеліцца на , то . У прыватнасці, .
* (a\cdot m, a\cdot n) = |a|\cdot (m, n) — агульны множнік можна выносіць за знак НАД.
* Калі D=(m, n), то пасля дзялення на D лікі становяцца ўзаемна простымі, г.зн. \left({\frac{m}{D},\frac{n}{D}}\right)=1. Гэта азначае, сярод іншага, што для прывядзення дробу да нескарачальнага выгляду трэба падзяліць яе лічнік і назоўнік на іх НАД.
* Мультыплікатыўнасць: калі a_1, a_2 узаемна простыя, то:
: (a_1 \cdot a_2, b) = (a_1, b) \cdot (a_2, b)
* Найбольшы агульны дзельнік лікаў  і  можна вызначыць як найменшы дадатны элемент мноства ўсіх іхніх :
:: \left\{ a\cdot m + b\cdot n\mid a,b\in\Z \right\},
: і таму (m,n) можна прадставіць у выглядзе лінейнай камбінацыі лікаў  і :
:: (m,n) = u\cdot m + v\cdot n.
: Гэта роўнасць называецца , а каэфіцыенты u і v — **каэфіцыентамі Безу**. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы \mathbb{Z}, спароджаная наборам \{a_1, a_2, \dots , a_n\}, —  і спараджаецца адным элементам: .

## Абагульненні 
Паняцце дзялімасці цэлых лікаў натуральным чынам абагульняецца на адвольныя , такія, як  ці гаусавы цэлыя лікі. Аднак, вызначыць  як *найбольшы* з агульных дзельнікаў  і  нельга, бо ў такіх колцах, увогуле кажучы, не вызначана дачыненне парадку. Таму ў якасці азначэння НАД бярэцца яго асноўная ўласцівасць:
:: **Найбольшым агульным дзельнікам**  называецца той агульны дзельнік, які дзеліцца на ўсе астатнія агульныя дзельнікі элементаў  і .
Для натуральных лікаў новае азначэнне раўназначнае старому. Для цэлых лікаў НАД у новым сэнсе ўжо не адназначны: процілеглы яму лік таксама будзе НАД. Для гаусавых лікаў колькасць розных НАД раўняецца ўжо чатыром.

НАД двух элементаў камутатыўнага колца, увогуле кажучы, можа не існаваць. Напрыклад, для наступных элементаў  і  колца \mathbb{Z}\left[\sqrt{-3}\right] не існуе найбольшага агульнага дзельніка:
: a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\qquad b = \left(1+\sqrt{-3}\right)\cdot 2.

У  найбольшы агульны дзельнік заўсёды існуе і вызначан з дакладнасцю да , г.зн. колькасць НАД роўная ліку дзельнікаў адзінкі ў колцы.

## Гл. таксама 
* Бінарны алгарытм вылічэння НАД
* Дзялімасць
* Еўклідава колца
* Найменшае агульнае кратнае

## Зноскі 
## Літаратура 
* 

Катэгорыя:Тэорыя лікаў