wd wp Пошук: ⬜

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

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

m ⋅ n .

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

$\{\displaystyle (m,n)\cdot [m,n]=m\cdot n.\}$ Гэта асобны выпадак больш агульнай тэарэмы: калі

, … ,

{\displaystyle a_{1},a_{2},\dots ,a_{n}}

$\{\displaystyle a_\{1\},a_\{2\},\dots ,a_\{n\}\}$ — ненулявыя лікі,

{\displaystyle D}

$\{\displaystyle D\}$ — якое-небудзь іх агульнае кратнае, то справядліва формула:

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).}

$\{\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 a_\{1\},a_\{2\},\dots a_\{k\}\}$ , дзе

k ≥ 2

{\displaystyle k\geq 2}

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

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

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

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

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

n

⋅ ⋯ ⋅

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

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

m

⋅ ⋯ ⋅

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

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

, … ,

{\displaystyle p_{1},\dots ,p_{k}}

$\{\displaystyle p_\{1\},\dots ,p_\{k\}\}$ — розныя простыя лікі, а

, … ,

{\displaystyle d_{1},\dots ,d_{k}}

$\{\displaystyle d_\{1\},\dots ,d_\{k\}\}$ і

, … ,

{\displaystyle e_{1},\dots ,e_{k}}

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

( n , m )

min (

)

⋅ ⋯ ⋅

min (

)

{\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\}^\{\min(d_\{1\},e_\{1\})\}\cdot \dots \cdot p_\{k\}^\{\min(d_\{k\},e_\{k\})\},\}$

[ n , m ]

max (

)

⋅ ⋯ ⋅

max (

)

{\displaystyle [n,m]=p_{1}^{\max(d_{1},e_{1})}\cdot \dots \cdot p_{k}^{\max(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 a_\{1\},a_\{2\},\dots a_\{n\}\}$ , іх НАД шукаюць па наступным алгарытме:

= (

)

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

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

= (

)

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

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

= (

n − 1

)

{\displaystyle d_{n}=(d_{n-1},a_{n})}

$\{\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.
( a ⋅ m , a ⋅ n ) =

⋅ ( m , n )

{\displaystyle (a\cdot m,a\cdot n)=|a|\cdot (m,n)}

$\{\displaystyle (a\cdot m,a\cdot n)=|a|\cdot (m,n)\}$ — агульны множнік можна выносіць за знак НАД.

Калі

D

( m , n )

{\displaystyle D=(m,n)}

$\{\displaystyle D=(m,n)\}$ , то пасля дзялення на

{\displaystyle D}

$\{\displaystyle D\}$ лікі становяцца ўзаемна простымі, г.зн.

(

m D

n D

)

= 1

{\displaystyle \left({{\frac {m}{D}},{\frac {n}{D}}}\right)=1}

$\{\displaystyle \left(\{\{\frac \{m\}\{D\}\},\{\frac \{n\}\{D\}\}\}\right)=1\}$ . Гэта азначае, сярод іншага, што для прывядзення дробу да нескарачальнага выгляду трэба падзяліць яе лічнік і назоўнік на іх НАД.

Мультыплікатыўнасць: калі

{\displaystyle a_{1},a_{2}}

$\{\displaystyle a_\{1\},a_\{2\}\}$ узаемна простыя, то:

(

⋅

, b )

(

, b ) ⋅ (

, b )

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

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

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

{

a ⋅ m + b ⋅ n ∣ a , b ∈

}

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

$\{\displaystyle \left\\{a\cdot m+b\cdot n\mid a,b\in \mathbb \{Z\} \right\\},\}$ і таму

( m , n )

{\displaystyle (m,n)}

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

( m , n )

u ⋅ m + v ⋅ n .

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

$\{\displaystyle (m,n)=u\cdot m+v\cdot n.\}$ Гэта роўнасць называецца суадносінамі Безу(руск.) бел., а каэфіцыенты

{\displaystyle u}

$\{\displaystyle u\}$ і

{\displaystyle v}

$\{\displaystyle v\}$ — каэфіцыентамі Безу. Каэфіцыенты Безу эфектыўна вылічаюцца пашыраным алгарытмам Еўкліда. Гэтае сцвярджэнне абагульняецца на наборы натуральных лікаў — яго сэнс у тым, што падгрупа групы

{\displaystyle \mathbb {Z} }

$\{\displaystyle \mathbb \{Z\} \}$ , спароджаная наборам

{

, … ,

}

{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}

$\{\displaystyle \\{a_\{1\},a_\{2\},\dots ,a_\{n\}\\}\}$ , — цыклічная(руск.) бел. і спараджаецца адным элементам: НАД(a1, a2, … , *a**n*). Абагульненні

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

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

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

[

− 3

]

{\displaystyle \mathbb {Z} \left[{\sqrt {-3}}\right]}

$\{\displaystyle \mathbb \{Z\} \left[\{\sqrt \{-3\}\}\right]\}$ не існуе найбольшага агульнага дзельніка:

a

4 2 ⋅ 2

(

1 +

− 3

)

(

1 −

− 3

)

b

(

1 +

− 3

)

⋅ 2.

{\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.}

$\{\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.\}$ У еўклідавых колцах(руск.) бел. найбольшы агульны дзельнік заўсёды існуе і вызначан з дакладнасцю да дзельнікаў адзінкі(руск.) бел., г.зн. колькасць НАД роўная ліку дзельнікаў адзінкі ў колцы.

Гл. таксама

Зноскі

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

Літаратура

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

Тэмы гэтай старонкі (3):
Катэгорыя·Вікіпедыя·Запыты на пераклад з рускай
Катэгорыя·Тэорыя лікаў
Катэгорыя·Вікіпедыя·Старонкі з модулем Hatnote з чырвонай спасылкай

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

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

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

( m , n ) ⋅ [ m , n ]

D

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

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

n

m

( n , m )

[ n , m ]

— гэта і ёсць шуканы НАД. Уласцівасці

D

, b )

( m , n )

, — цыклічная(руск.) бел. і спараджаецца адным элементам: НАД(a1, a2, … , a**n). Абагульненні

a

4

2 ⋅ 2

b

Гл. таксама

Зноскі

Літаратура

$\{\displaystyle d_\{n\}=(d_\{n-1\},a_\{n\})\}$ — гэта і ёсць шуканы НАД. Уласцівасці

$\{\displaystyle \\{a_\{1\},a_\{2\},\dots ,a_\{n\}\\}\}$ , — цыклічная(руск.) бел. і спараджаецца адным элементам: НАД(a1, a2, … , *a**n*). Абагульненні