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

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

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

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

• НАД(m, n)
• (m, n)
• gcd(m, n) (ад англ. Greatest Common Divisor)
• hcf(m, n) (ад брыт. англ. Highest Common Factor)

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

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

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

Асноўны артыкул: Найменшае агульнае кратнае

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

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

$(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).$

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

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

Лікі m і n называюцца ўзаемна-простымі, калі ў іх няма агульных дзельнікаў, акрамя адзінкі. Для такіх лікаў НАД(m, n) = 1. І наадварот, калі НАД(m, n) = 1, то лікі ўзаемна простыя.

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

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

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

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

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

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

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

Уласцівасці

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

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

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

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

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

Гэта роўнасць называецца суадносінамі Безу, а каэфіцыенты $u$ і $v$ — каэфіцыентамі Безу. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы $\mathbb {Z}$, спароджаная наборам $\{a_{1},a_{2},\dots ,a_{n}\}$, — цыклічная і спараджаецца адным элементам: НАД(a₁, a₂, … , a_n).

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

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

Найбольшым агульным дзельнікам НАД(a, b) называецца той агульны дзельнік, які дзеліцца на ўсе астатнія агульныя дзельнікі элементаў a і b.

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

НАД двух элементаў камутатыўнага колца, увогуле кажучы, можа не існаваць. Напрыклад, для наступных элементаў a і b колца $\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.$

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

Гл. таксама

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

Літаратура

• Виноградов И. М. Основы теории чисел.. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.