Прагляд зыходнага тэксту старонкі Найбольшы агульны дзельнік

'''Найбольшы агу́льны дзе́льнік''' ('''НАД''') двух [[цэлы лік|цэлых лікаў]] {{math|''m''}} і {{math|''n''}} — самы вялікі [[натуральны лік]], які дзеліць і {{math|''m''}}, і {{math|''n''}}. Іншымі словамі, гэта самы вялікі з іх [[Агульны дзельнік|агульных дзельнікаў]]<ref>{{кніга |загаловак=Математическая энциклопедия (в 5 томах) |месца=М. |год=1982 |том=3 |спасылка=http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t3.djvu |выдавецтва=Советская Энциклопедия}} старонка 857</ref>. Прыклад: для лікаў 70 і 105 найбольшы агульны дзельнік роўны 35.

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

Сустракаюцца наступныя абазначэнні найбольшага агульнага дзельніка {{math|''m''}} і {{math|''n''}}:
* {{math|НАД(''m'', ''n'')}}
* {{math|(''m'', ''n'')}}
* {{math|gcd(''m'', ''n'')}} (ад англ. ''Greatest Common Divisor'')
* {{math|hcf(''m'', ''n'')}} (ад {{нп3|Брытанская англійская мова|брыт. англ.|en|British English}} ''Highest Common Factor'')

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

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

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

НАК ненулявых лікаў {{math|''m''}} і {{math|''n''}} заўсёды існуе і звязаны з НАД наступнымі суадносінамі:
: <math>(m,n)\cdot[m,n]=m\cdot n.</math>

Гэта асобны выпадак больш агульнай тэарэмы:
калі <math>a_1, a_2, \dots , a_n</math> — ненулявыя лікі, <math>D</math> — якое-небудзь іх агульнае кратнае, то справядліва формула:
: <math>D = [a_1, a_2, \dots , a_n] \cdot \left(\frac{D}{a_1}, \frac{D}{a_2}, \dots , \frac{D}{a_n}\right).</math>

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

Падобным чынам, [[цэлы лік|цэлыя лікі]] <math>a_1, a_2, \dots a_k</math>, дзе <math>k\geq 2</math>, называюцца '''ўзаемна простымі''', калі іх найбольшы агульны дзельнік роўны [[1 (лік)|адзінцы]].

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

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

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

Акрамя таго, значэнне {{math|НАД(''m'', ''n'')}} можна лёгка вылічыць, калі вядома [[кананічнае раскладанне]] лікаў {{math|''m''}} і {{math|''n''}} на [[просты лік|простыя]] множнікі:
:: <math>n=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},</math>
:: <math>m=p_1^{e_1}\cdot \dots \cdot p_k^{e_k},</math>
дзе <math>p_1,\dots,p_k</math> — розныя простыя лікі, а <math>d_1,\dots,d_k</math> і <math>e_1,\dots,e_k</math> — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведны просты адсутнічае ў раскладанні). Тады {{math|НАД(''m'', ''n'')}} і {{math|НАК(''m'', ''n'')}} выражаюцца формуламі:
:: <math>(n,m)=p_1^{\min(d_1,e_1)}\cdot\dots\cdot p_k^{\min(d_k,e_k)},</math>
:: <math>[n,m]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.</math>

Калі лікаў больш чым два: <math>a_1, a_2,\dots a_n</math>, іх НАД шукаюць па наступным алгарытме:
: <math>d_2=(a_1, a_2)</math>
: <math>d_3=(d_2, a_3)</math>
:: <big>………</big>
: <math>d_n=(d_{n-1}, a_n)</math> — гэта і ёсць шуканы НАД.

== Уласцівасці ==
* Асноўная ўласцівасць: найбольшы агульны дзельнік {{math|''m''}} і {{math|''n''}} дзеліцца на любы агульны дзельнік гэтых лікаў. Прыклад: для лікаў 12 і 18 найбольшы агульны дзельнік ровен 6; ён дзеліцца на ўсе агульныя дзельнікі гэтых лікаў: 1, 2, 3, 6.
** Вынік 1: мноства агульных дзельнікаў {{math|''m''}} і {{math|''n''}} супадае з мноствам дзельнікаў {{math|НАД(''m'', ''n'')}}.
** Вынік 2: мноства агульных кратных {{math|''m''}} і {{math|''n''}} супадае з мноствам кратных {{math|НАК(''m'', ''n'')}}.
* Калі {{math|''m''}} дзеліцца на {{math|''n''}}, то {{math|НАД(''m'', ''n'') {{=}} ''n''}}. У прыватнасці, {{math|НАД(''n'', ''n'') {{=}} ''n''}}.
* <math>(a\cdot m, a\cdot n) = |a|\cdot (m, n)</math> — агульны множнік можна выносіць за знак НАД.
* Калі <math>D=(m, n)</math>, то пасля дзялення на <math>D</math> лікі становяцца ўзаемна простымі, г.зн. <math>\left({\frac{m}{D},\frac{n}{D}}\right)=1</math>. Гэта азначае, сярод іншага, што для прывядзення [[дроб]]у да нескарачальнага выгляду трэба падзяліць яе [[лічнік дробу|лічнік]] і [[назоўнік дробу|назоўнік]] на іх НАД.
* [[Мультыплікатыўнасць]]: калі <math>a_1, a_2</math> узаемна простыя, то:
: <math>(a_1 \cdot a_2, b) = (a_1, b) \cdot (a_2, b)</math>
* Найбольшы агульны дзельнік лікаў {{math|''m''}} і {{math|''n''}} можна вызначыць як найменшы дадатны элемент мноства ўсіх іхніх {{нп3|лінейная камбінацыя|лінейных камбінацый|ru|Линейная комбинация}}:
:: <math>\left\{ a\cdot m + b\cdot n\mid a,b\in\Z \right\},</math>
: і таму <math>(m,n)</math> можна прадставіць у выглядзе лінейнай камбінацыі лікаў {{math|''m''}} і {{math|''n''}}:
:: <math>(m,n) = u\cdot m + v\cdot n.</math>
: Гэта роўнасць называецца {{нп3|суадносіны Безу|'''суадносінамі Безу'''|ru|Соотношение Безу}}, а каэфіцыенты <math>u</math> і <math>v</math> — '''каэфіцыентамі Безу'''. Каэфіцыенты Безу эфектыўна вылічаюцца [[Пашыраны алгарытм Еўкліда|пашыраным алгарытмам Еўкліда]]. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа [[Група (алгебра)|групы]] <math>\mathbb{Z}</math>, спароджаная наборам <math>\{a_1, a_2, \dots , a_n\}</math>, — {{нп3|Цыклічная группа|цыклічная|ru|Циклическая группа}} і спараджаецца адным элементам: {{math|НАД(''a''<sub>1</sub>, ''a''<sub>2</sub>, … , ''a''<sub>''n''</sub>)}}.

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

Паняцце дзялімасці цэлых лікаў натуральным чынам абагульняецца на адвольныя {{нп3|камутатыўнае колца|камутатыўныя колцы|ru|Коммутативное кольцо}}, такія, як {{нп3|колца мнагачленаў||ru|Кольцо многочленов}} ці [[гаусавы цэлыя лікі]]. Аднак, вызначыць {{math|НАД(''a'', ''b'')}} як ''найбольшы'' з агульных дзельнікаў {{math|''a''}} і {{math|''b''}} нельга, бо ў такіх колцах, увогуле кажучы, не вызначана [[дачыненне парадку]]. Таму ў якасці азначэння НАД бярэцца яго асноўная ўласцівасць:
:: '''Найбольшым агульным дзельнікам''' {{math|НАД(''a'', ''b'')}} называецца той агульны дзельнік, які дзеліцца на ўсе астатнія агульныя дзельнікі элементаў {{math|''a''}} і {{math|''b''}}.
Для натуральных лікаў новае азначэнне раўназначнае старому. Для цэлых лікаў НАД у новым сэнсе ўжо не адназначны: процілеглы яму лік таксама будзе НАД. Для гаусавых лікаў колькасць розных НАД раўняецца ўжо чатыром.

НАД двух элементаў камутатыўнага колца, увогуле кажучы, можа не існаваць. Напрыклад, для наступных элементаў {{math|''a''}} і {{math|''b''}} колца <math>\mathbb{Z}\left[\sqrt{-3}\right]</math> не існуе найбольшага агульнага дзельніка:
: <math>a = 4 = 2\cdot 2 = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right),\qquad b = \left(1+\sqrt{-3}\right)\cdot 2.</math>

У {{нп3|Еўклідава колца|еўклідавых колцах|ru|Евклидово кольцо}} найбольшы агульны дзельнік заўсёды існуе і вызначан з дакладнасцю да {{нп3|абарачальны элемент|дзельнікаў адзінкі|ru|Обратимый элемент}}, г.зн. колькасць НАД роўная ліку дзельнікаў адзінкі ў колцы.

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

== Зноскі ==
{{reflist}}

== Літаратура ==
* {{кніга|аўтар=Виноградов И. М.|спасылка=http://math.ru/lib/book/djvu/vinogradov.djvu|загаловак=Основы теории чисел. | месца=М.-Л. |выдавецтва=Гос. изд. технико-теоретической литературы |год= 1952 |старонак = 180}}

[[Катэгорыя:Тэорыя лікаў]]