wd wp Пошук: ⬜

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

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

НАК(m, n);
[m, n];
lcm(m, n) (ад англ.: Least Common Multiple).

Прыклад: НАК(16, 20) = 80.

Найменшае агульнае кратнае некалькіх лікаў — гэта найменшы натуральны лік, які дзеліцца на кожны з гэтых лікаў.

Адно з найбольш частых прымяненняў НАК — прывядзенне дробаў да агульнага назоўніка.

Уласцівасці

Перастаўляльнасць (камутатыўнасць):

lcm ⁡ ( a , b )

lcm ⁡ ( b , a ) .

{\displaystyle \operatorname {lcm} (a,b)=\operatorname {lcm} (b,a).}

$\{\displaystyle \operatorname \{lcm\} (a,b)=\operatorname \{lcm\} (b,a).\}$

Спалучальнасць (асацыятыўнасць):

lcm ⁡ ( a , lcm ⁡ ( b , c ) )

lcm ⁡ ( lcm ⁡ ( a , b ) , c ) .

{\displaystyle \operatorname {lcm} (a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\operatorname {lcm} (a,b),c).}

$\{\displaystyle \operatorname \{lcm\} (a,\operatorname \{lcm\} (b,c))=\operatorname \{lcm\} (\operatorname \{lcm\} (a,b),c).\}$

Сувязь з найбольшым агульным дзельнікам gcd(a, b):

lcm ⁡ ( a , b )

a ⋅ b

gcd ⁡ ( a , b )

{\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.}

$\{\displaystyle \operatorname \{lcm\} (a,b)=\{\frac \{|a\cdot b|\}\{\operatorname \{gcd\} (a,b)\}\}.\}$

У прыватнасці, калі a і b — узаемна простыя лікі(руск.) бел., то:

lcm ⁡ ( a , b )

a ⋅ b .

{\displaystyle \operatorname {lcm} (a,b)=a\cdot b.}

$\{\displaystyle \operatorname \{lcm\} (a,b)=a\cdot b.\}$

lcm ⁡ (

, . . . ,

)

( lcm ⁡ (

, . . . ,

)

{\displaystyle \operatorname {lcm} (a_{1}^{n},a_{2}^{n},…,a_{k}^{n})=(\operatorname {lcm} (a_{1},a_{2},…,a_{k}))^{n}}

$\{\displaystyle \operatorname \{lcm\} (a_\{1\}^\{n\},a_\{2\}^\{n\},…,a_\{k\}^\{n\})=(\operatorname \{lcm\} (a_\{1\},a_\{2\},…,a_\{k\}))^\{n\}\}$ пры

n ⩾ 0.

{\displaystyle n\geqslant 0.}

$\{\displaystyle n\geqslant 0.\}$

Найменшае агульнае кратнае двух цэлых лікаў m і n з’яўляецца дзельнікам усіх іншых агульных кратных m і n. Больш таго, мноства агульных кратных m і n супадае з мноствам кратных для НАК(m, n).
Асімптотыкі для

lcm ⁡ ( 1 , 2 , … , n )

{\displaystyle \operatorname {lcm} (1,2,\ldots ,n)}

$\{\displaystyle \operatorname \{lcm\} (1,2,\ldots ,n)\}$ можна выразіць праз некаторыя тэарэтыка-лікавыя функцыі. + Функцыя Чабышова(англ.) бел.

ψ
(
x
)
=
ln
⁡
lcm
⁡
(
1
,
2
,
…
,
⌊
x
⌋
)
.


\{\displaystyle \psi (x)=\ln \operatorname \{lcm\} (1,2,\ldots ,\lfloor x\rfloor ).\}

![\{\displaystyle \psi (x)=\ln \operatorname \{lcm\} (1,2,\ldots ,\lfloor x\rfloor ).\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/103e908bfb7add50083a4f3b6b76738bbf40dcc7)
+ lcm
⁡
(
1
,
2
,
…
,
n
)
⩽
g

(



n
(
n
+
1
)

2


)

∼

e





n
(
n
+
1
)

2


ln
⁡



n
(
n
+
1
)

2







\{\displaystyle \operatorname \{lcm\} (1,2,\ldots ,n)\leqslant g\left(\{\frac \{n(n+1)\}\{2\}\}\right)\sim e^\{\sqrt \{\{\frac \{n(n+1)\}\{2\}\}\ln \{\frac \{n(n+1)\}\{2\}\}\}\}\}

![\{\displaystyle \operatorname \{lcm\} (1,2,\ldots ,n)\leqslant g\left(\{\frac \{n(n+1)\}\{2\}\}\right)\sim e^\{\sqrt \{\{\frac \{n(n+1)\}\{2\}\}\ln \{\frac \{n(n+1)\}\{2\}\}\}\}\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f30ff04dca4d4781aff9905db4166666f4db9dc). Гэта вынікае з азначэння і ўласцівасцей [функцыі Ландау](https://ru.wikipedia.org/wiki/Функция%20Ландау "ru:Функция Ландау")(руск.) [бел.](/Функцыя_Ландау "Функцыя Ландау") *g(n)*.
+ lcm
⁡
(
1
,
2
,
…
,
n
)
∼

e

n
+
o
(
1
)




\{\displaystyle \operatorname \{lcm\} (1,2,\ldots ,n)\sim e^\{n+o(1)\}\}

![\{\displaystyle \operatorname \{lcm\} (1,2,\ldots ,n)\sim e^\{n+o(1)\}\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6602b0ce9e1cf0b9119fd272cc20b8c041999f2c), што вынікае з [закона размеркавання простых лікаў](https://ru.wikipedia.org/wiki/Теорема%20о%20распределении%20простых%20чисел "ru:Теорема о распределении простых чисел")(руск.) [бел.](/Тэарэма_аб_размеркаванні_простых_лікаў "Тэарэма аб размеркаванні простых лікаў").

Вылічэнне НАК

НАК(a, b) можна вылічыць некалькімі спосабамі.

Калі вядомы найбольшы агульны дзельнік, можна выкарыстаць яго сувязь з НАК:

lcm ⁡ ( a , b )

a ⋅ b

gcd ⁡ ( a , b )

{\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}}

$\{\displaystyle \operatorname \{lcm\} (a,b)=\{\frac \{|a\cdot b|\}\{\operatorname \{gcd\} (a,b)\}\}\}$ 2. Няхай вядома кананічнае раскладанне абодвух лікаў на простыя множнікі:

a

⋅ ⋯ ⋅

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

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

b

⋅ ⋯ ⋅

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

$\{\displaystyle b=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\}\}$ — неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведнага простага няма ў раскладанні). Тады НАК(a, b) вылічаецца па формуле:

[ a , b ]

max (

)

⋅ ⋯ ⋅

max (

)

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

$\{\displaystyle [a,b]=p_\{1\}^\{\max(d_\{1\},e_\{1\})\}\cdot \dots \cdot p_\{k\}^\{\max(d_\{k\},e_\{k\})\}.\}$ Іншымі словамі, раскладанне НАК утрымлівае ўсе простыя множнікі, якія ўваходзяць хоць у адно з раскладанняў лікаў a і b, прычым з двух паказчыкаў ступені гэтага множніка бярэцца найбольшы. Прыклад:

⋅

{\displaystyle 8;,;,=2^{3}\cdot 3^{0}\cdot 5^{0}\cdot 7^{0},!}

$\{\displaystyle 8\;\,\;\,=2^\{3\}\cdot 3^\{0\}\cdot 5^\{0\}\cdot 7^\{0\}\,\!\}$

⋅

{\displaystyle 9;,;,=2^{0}\cdot 3^{2}\cdot 5^{0}\cdot 7^{0},!}

$\{\displaystyle 9\;\,\;\,=2^\{0\}\cdot 3^\{2\}\cdot 5^\{0\}\cdot 7^\{0\}\,\!\}$

⋅

{\displaystyle 21;,=2^{0}\cdot 3^{1}\cdot 5^{0}\cdot 7^{1}.,!}

$\{\displaystyle 21\;\,=2^\{0\}\cdot 3^\{1\}\cdot 5^\{0\}\cdot 7^\{1\}.\,\!\}$

lcm ⁡ ( 8 , 9 , 21 )

⋅

= 8 ⋅ 9 ⋅ 1 ⋅ 7

{\displaystyle \operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 5^{0}\cdot 7^{1}=8\cdot 9\cdot 1\cdot 7=504.,!}

$\{\displaystyle \operatorname \{lcm\} (8,9,21)=2^\{3\}\cdot 3^\{2\}\cdot 5^\{0\}\cdot 7^\{1\}=8\cdot 9\cdot 1\cdot 7=504.\,\!\}$ Вылічэнне найменшага агульнага кратнага некалькіх лікаў можна звесці да некалькіх паслядоўных вылічэнняў НАК ад двух лікаў:

lcm ⁡ ( a , b , c ) = lcm ⁡ ( lcm ⁡ ( a , b ) , c ) ;

{\displaystyle \operatorname {lcm} (a,b,c)=\operatorname {lcm} (\operatorname {lcm} (a,b),c);}

$\{\displaystyle \operatorname \{lcm\} (a,b,c)=\operatorname \{lcm\} (\operatorname \{lcm\} (a,b),c);\}$

lcm ⁡ (

, … ,

)

lcm ⁡ ( lcm ⁡ (

, … ,

n − 1

) ,

) .

{\displaystyle \operatorname {lcm} (a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{n-1}),a_{n}).}

$\{\displaystyle \operatorname \{lcm\} (a_\{1\},a_\{2\},\ldots ,a_\{n\})=\operatorname \{lcm\} (\operatorname \{lcm\} (a_\{1\},a_\{2\},\ldots ,a_\{n-1\}),a_\{n\}).\}$

Гл. таксама

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

Літаратура

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

Спасылкі

Weisstein, Eric W. Least Common Multiple(англ.) на старонцы Wolfram MathWorld.

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