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

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

Найбольшы агу́льны дзе́льнік (НАД) двух цэлых лікаў 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)\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\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\}, — цыклічная(руск.) бел. і спараджаецца адным элементам: НАД(a1, a2, … , an).

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

Паняцце дзялімасці цэлых лікаў натуральным чынам абагульняецца на адвольныя камутатыўныя колцы(руск.) бел., такія, як колца мнагачленаў(руск.) бел. ці гаусавы цэлыя лікі. Аднак, вызначыць НАД(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.

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

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

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

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

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