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

З Вікіпедыі, свабоднай энцыклапедыі

Найбольшы агу́льны дзе́льнік (НАД) двух цэлых лікаў 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 заўсёды існуе і звязаны з НАД наступнымі суадносінамі:

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

Узаемна простыя лікі[правіць | правіць зыходнік]

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

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

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

Спосабы вылічэння[правіць | правіць зыходнік]

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

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

дзе  — розныя простыя лікі, а і  — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведны просты адсутнічае ў раскладанні). Тады НАД(m, n) і НАК(m, 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.
  •  — агульны множнік можна выносіць за знак НАД.
  • Калі , то пасля дзялення на лікі становяцца ўзаемна простымі, г.зн. . Гэта азначае, сярод іншага, што для прывядзення дробу да нескарачальнага выгляду трэба падзяліць яе лічнік і назоўнік на іх НАД.
  • Мультыплікатыўнасць: калі узаемна простыя, то:
  • Найбольшы агульны дзельнік лікаў m і n можна вызначыць як найменшы дадатны элемент мноства ўсіх іхніх лінейных камбінацый  (руск.):
і таму можна прадставіць у выглядзе лінейнай камбінацыі лікаў m і n:
Гэта роўнасць называецца суадносінамі Безу  (руск.), а каэфіцыенты і  — каэфіцыентамі Безу. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы , спароджаная наборам , — цыклічная  (руск.) і спараджаецца адным элементам: НАД(a1, a2, … , an).

Абагульненні[правіць | правіць зыходнік]

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

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

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

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

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

Гл. таксама[правіць | правіць зыходнік]

Зноскі[правіць | правіць зыходнік]

  1. Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. старонка 857

Літаратура[правіць | правіць зыходнік]