Найбольшы агу́льны дзе́льнік (НАД) двух цэлых лікаў і — самы вялікі натуральны лік, які дзеліць і , і . Іншымі словамі, гэта самы вялікі з іх агульных дзельнікаў старонка 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: мноства агульных кратных і супадае з мноствам кратных . Калі дзеліцца на , то . У прыватнасці, . — агульны множнік можна выносіць за знак НАД. Калі , то пасля дзялення на лікі становяцца ўзаемна простымі, г.зн. . Гэта азначае, сярод іншага, што для прывядзення дробу да нескарачальнага выгляду трэба падзяліць яе лічнік і назоўнік на іх НАД. Мультыплікатыўнасць: калі узаемна простыя, то:
Найбольшы агульны дзельнік лікаў і можна вызначыць як найменшы дадатны элемент мноства ўсіх іхніх :
і таму можна прадставіць у выглядзе лінейнай камбінацыі лікаў і :
Гэта роўнасць называецца , а каэфіцыенты і — каэфіцыентамі Безу. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы , спароджаная наборам , — і спараджаецца адным элементам: .
Абагульненні
Паняцце дзялімасці цэлых лікаў натуральным чынам абагульняецца на адвольныя , такія, як ці гаусавы цэлыя лікі. Аднак, вызначыць як найбольшы з агульных дзельнікаў і нельга, бо ў такіх колцах, увогуле кажучы, не вызначана дачыненне парадку. Таму ў якасці азначэння НАД бярэцца яго асноўная ўласцівасць: Найбольшым агульным дзельнікам называецца той агульны дзельнік, які дзеліцца на ўсе астатнія агульныя дзельнікі элементаў і . Для натуральных лікаў новае азначэнне раўназначнае старому. Для цэлых лікаў НАД у новым сэнсе ўжо не адназначны: процілеглы яму лік таксама будзе НАД. Для гаусавых лікаў колькасць розных НАД раўняецца ўжо чатыром.
НАД двух элементаў камутатыўнага колца, увогуле кажучы, можа не існаваць. Напрыклад, для наступных элементаў і колца не існуе найбольшага агульнага дзельніка:
У найбольшы агульны дзельнік заўсёды існуе і вызначан з дакладнасцю да , г.зн. колькасць НАД роўная ліку дзельнікаў адзінкі ў колцы.
Гл. таксама Бінарны алгарытм вылічэння НАД Дзялімасць Еўклідава колца Найменшае агульнае кратнае
Зноскі
Літаратура
Катэгорыя:Тэорыя лікаў