Найме́ншае агу́льнае кра́тнае (найменшы агульны кратны лік , НАК ) двух цэлых лікаў 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).}
Спалучальнасць (асацыятыўнасць):
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).}
Сувязь з найбольшым агульным дзельнікам gcd(a , b ) :
lcm
(
a
,
b
)
=
|
a
⋅
b
|
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.}
lcm
(
a
1
n
,
a
2
n
,
.
.
.
,
a
k
n
)
=
(
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.}
Найменшае агульнае кратнае двух цэлых лікаў m і n з'яўляецца дзельнікам усіх іншых агульных кратных m і n . Больш таго, мноства агульных кратных m і n супадае з мноствам кратных для НАК(m , n ) .
Асімптотыкі для
lcm
(
1
,
2
,
…
,
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 ).}
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}}}}}
. Гэта вынікае з азначэння і ўласцівасцей функцыі Ландау (руск.) ( бел. g(n) .
lcm
(
1
,
2
,
…
,
n
)
∼
e
n
+
o
(
1
)
{\displaystyle \operatorname {lcm} (1,2,\ldots ,n)\sim e^{n+o(1)}}
, што вынікае з закона размеркавання простых лікаў (руск.) ( бел. .
НАК(a , b ) можна вылічыць некалькімі спосабамі.
1. Калі вядомы найбольшы агульны дзельнік , можна выкарыстаць яго сувязь з НАК:
lcm
(
a
,
b
)
=
|
a
⋅
b
|
gcd
(
a
,
b
)
{\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}}
2. Няхай вядома кананічнае раскладанне абодвух лікаў на простыя множнікі:
a
=
p
1
d
1
⋅
⋯
⋅
p
k
d
k
,
{\displaystyle a=p_{1}^{d_{1}}\cdot \dots \cdot p_{k}^{d_{k}},}
b
=
p
1
e
1
⋅
⋯
⋅
p
k
e
k
,
{\displaystyle b=p_{1}^{e_{1}}\cdot \dots \cdot p_{k}^{e_{k}},}
дзе
p
1
,
…
,
p
k
{\displaystyle p_{1},\dots ,p_{k}}
— розныя простыя лікі, а
d
1
,
…
,
d
k
{\displaystyle d_{1},\dots ,d_{k}}
і
e
1
,
…
,
e
k
{\displaystyle e_{1},\dots ,e_{k}}
— неадмоўныя цэлыя лікі (яны могуць быць нулямі, калі адпаведнага простага няма ў раскладанні). Тады НАК(a , b ) вылічаецца па формуле:
[
a
,
b
]
=
p
1
max
(
d
1
,
e
1
)
⋅
⋯
⋅
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 , прычым з двух паказчыкаў ступені гэтага множніка бярэцца найбольшы. Прыклад:
8
=
2
3
⋅
3
0
⋅
5
0
⋅
7
0
{\displaystyle 8\;\,\;\,=2^{3}\cdot 3^{0}\cdot 5^{0}\cdot 7^{0}\,\!}
9
=
2
0
⋅
3
2
⋅
5
0
⋅
7
0
{\displaystyle 9\;\,\;\,=2^{0}\cdot 3^{2}\cdot 5^{0}\cdot 7^{0}\,\!}
21
=
2
0
⋅
3
1
⋅
5
0
⋅
7
1
.
{\displaystyle 21\;\,=2^{0}\cdot 3^{1}\cdot 5^{0}\cdot 7^{1}.\,\!}
lcm
(
8
,
9
,
21
)
=
2
3
⋅
3
2
⋅
5
0
⋅
7
1
=
8
⋅
9
⋅
1
⋅
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);}
lcm
(
a
1
,
a
2
,
…
,
a
n
)
=
lcm
(
lcm
(
a
1
,
a
2
,
…
,
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 с.