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

Найбольшы агу́льны дзе́льнік (НАД) двух цэлых лікаў m і n — самы вялікі натуральны лік, які дзеліць і m, і n. Іншымі словамі, гэта самы вялікі з іх агульных дзельнікаў^[1]. Прыклад: для лікаў 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 заўсёды існуе і звязаны з НАД наступнымі суадносінамі:

${\displaystyle (m,n)\cdot [m,n]=m\cdot n.}$

Гэта асобны выпадак больш агульнай тэарэмы: калі ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ — ненулявыя лікі, ${\displaystyle D}$ — якое-небудзь іх агульнае кратнае, то справядліва формула:

${\displaystyle 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, то лікі ўзаемна простыя.

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

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

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

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

${\displaystyle n=p_{1}^{d_{1}}\cdot \dots \cdot p_{k}^{d_{k}},}$

${\displaystyle m=p_{1}^{e_{1}}\cdot \dots \cdot p_{k}^{e_{k}},}$

дзе ${\displaystyle p_{1},\dots ,p_{k}}$ — розныя простыя лікі, а ${\displaystyle d_{1},\dots ,d_{k}}$ і ${\displaystyle e_{1},\dots ,e_{k}}$ — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведны просты адсутнічае ў раскладанні). Тады НАД(m, n) і НАК(m, n) выражаюцца формуламі:

${\displaystyle (n,m)=p_{1}^{\min(d_{1},e_{1})}\cdot \dots \cdot p_{k}^{\min(d_{k},e_{k})},}$

${\displaystyle [n,m]=p_{1}^{\max(d_{1},e_{1})}\cdot \dots \cdot p_{k}^{\max(d_{k},e_{k})}.}$

Калі лікаў больш чым два: ${\displaystyle a_{1},a_{2},\dots a_{n}}$, іх НАД шукаюць па наступным алгарытме:

${\displaystyle d_{2}=(a_{1},a_{2})}$

${\displaystyle d_{3}=(d_{2},a_{3})}$

………

${\displaystyle 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.
• ${\displaystyle (a\cdot m,a\cdot n)=|a|\cdot (m,n)}$ — агульны множнік можна выносіць за знак НАД.
• Калі ${\displaystyle D=(m,n)}$, то пасля дзялення на ${\displaystyle D}$ лікі становяцца ўзаемна простымі, г.зн. ${\displaystyle \left({{\frac {m}{D}},{\frac {n}{D}}}\right)=1}$. Гэта азначае, сярод іншага, што для прывядзення дробу да нескарачальнага выгляду трэба падзяліць яе лічнік і назоўнік на іх НАД.
• Мультыплікатыўнасць: калі ${\displaystyle a_{1},a_{2}}$ узаемна простыя, то:

${\displaystyle (a_{1}\cdot a_{2},b)=(a_{1},b)\cdot (a_{2},b)}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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 с.