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

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

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

Сустракаюцца наступныя абазначэнні найбольшага агульнага дзельніка  і :


  (ад англ. Greatest Common Divisor)
  (ад  Highest Common Factor)

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

 Звязаныя азначэнні 

 Найменшае агульнае кратнае 

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

НАК ненулявых лікаў  і  заўсёды існуе і звязаны з НАД наступнымі суадносінамі:


Гэта асобны выпадак больш агульнай тэарэмы:
калі  — ненулявыя лікі,  — якое-небудзь іх агульнае кратнае, то справядліва формула:


 Узаемна простыя лікі 

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

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

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

 Спосабы вылічэння 

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

Акрамя таго, значэнне  можна лёгка вылічыць, калі вядома кананічнае раскладанне лікаў  і  на простыя множнікі:


дзе  — розныя простыя лікі, а  і  — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведны просты адсутнічае ў раскладанні). Тады  і  выражаюцца формуламі:



Калі лікаў больш чым два: , іх НАД шукаюць па наступным алгарытме:


 ………
  — гэта і ёсць шуканы НАД.

 Уласцівасці 
 Асноўная ўласцівасць: найбольшы агульны дзельнік  і  дзеліцца на любы агульны дзельнік гэтых лікаў. Прыклад: для лікаў 12 і 18 найбольшы агульны дзельнік ровен 6; ён дзеліцца на ўсе агульныя дзельнікі гэтых лікаў: 1, 2, 3, 6.
 Вынік 1: мноства агульных дзельнікаў  і  супадае з мноствам дзельнікаў .
 Вынік 2: мноства агульных кратных  і  супадае з мноствам кратных .
 Калі  дзеліцца на , то . У прыватнасці, .
  — агульны множнік можна выносіць за знак НАД.
 Калі , то пасля дзялення на  лікі становяцца ўзаемна простымі, г.зн. . Гэта азначае, сярод іншага, што для прывядзення дробу да нескарачальнага выгляду трэба падзяліць яе лічнік і назоўнік на іх НАД.
 Мультыплікатыўнасць: калі  узаемна простыя, то:

 Найбольшы агульны дзельнік лікаў  і  можна вызначыць як найменшы дадатны элемент мноства ўсіх іхніх :

 і таму  можна прадставіць у выглядзе лінейнай камбінацыі лікаў  і :

 Гэта роўнасць называецца , а каэфіцыенты  і  — каэфіцыентамі Безу. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы , спароджаная наборам , —  і спараджаецца адным элементам: .

 Абагульненні 

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

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


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

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

 Зноскі 

 Літаратура 


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