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

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

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

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

• Шаблон:Math
• Шаблон:Math
• Шаблон:Math (ад англ. Greatest Common Divisor)
• Шаблон:Math (ад Шаблон:Нп3 Highest Common Factor)

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

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

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

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

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

$(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 (\frac{D}{a_1},\frac{D}{a_2},\dots ,\frac{D}{a_n}).$

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

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

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

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

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

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

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

$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$ — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведны просты адсутнічае ў раскладанні). Тады Шаблон:Math і Шаблон:Math выражаюцца формуламі:

$(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)$ — гэта і ёсць шуканы НАД.

Уласцівасці

• Асноўная ўласцівасць: найбольшы агульны дзельнік Шаблон:Math і Шаблон:Math дзеліцца на любы агульны дзельнік гэтых лікаў. Прыклад: для лікаў 12 і 18 найбольшы агульны дзельнік ровен 6; ён дзеліцца на ўсе агульныя дзельнікі гэтых лікаў: 1, 2, 3, 6.
  • Вынік 1: мноства агульных дзельнікаў Шаблон:Math і Шаблон:Math супадае з мноствам дзельнікаў Шаблон:Math.
  • Вынік 2: мноства агульных кратных Шаблон:Math і Шаблон:Math супадае з мноствам кратных Шаблон:Math.
• Калі Шаблон:Math дзеліцца на Шаблон:Math, то Шаблон:Math. У прыватнасці, Шаблон:Math.
• $(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)$

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

$\{a\cdot m+b\cdot n\mid a,b\in \mathbb{Z}\},$

і таму $(m,n)$ можна прадставіць у выглядзе лінейнай камбінацыі лікаў Шаблон:Math і Шаблон:Math:

$(m,n)=u\cdot m+v\cdot n.$

Гэта роўнасць называецца Шаблон:Нп3, а каэфіцыенты $u$ і $v$ — каэфіцыентамі Безу. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы $\mathbb{Z}$, спароджаная наборам $\{a_1,a_2,\dots ,a_n\}$, — Шаблон:Нп3 і спараджаецца адным элементам: Шаблон:Math.

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

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

Найбольшым агульным дзельнікам Шаблон:Math называецца той агульны дзельнік, які дзеліцца на ўсе астатнія агульныя дзельнікі элементаў Шаблон:Math і Шаблон:Math.

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

НАД двух элементаў камутатыўнага колца, увогуле кажучы, можа не існаваць. Напрыклад, для наступных элементаў Шаблон:Math і Шаблон:Math колца $\mathbb{Z}\left[\sqrt{-3}\right]$ не існуе найбольшага агульнага дзельніка:

$a=4=2\cdot 2=(1+\sqrt{-3})(1-\sqrt{-3}),b=(1+\sqrt{-3})\cdot 2.$

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

Гл. таксама

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

Літаратура

• Шаблон:Кніга