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

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

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

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

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

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

Уласцівасці

• Перастаўляльнасць (камутатыўнасць): $\operatorname {lcm} (a,b)=\operatorname {lcm} (b,a).$
• Спалучальнасць (асацыятыўнасць): $\operatorname {lcm} (a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\operatorname {lcm} (a,b),c).$
• Сувязь з найбольшым агульным дзельнікам gcd(a, b):

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

• У прыватнасці, калі a і b — узаемна простыя лікі, то: $\operatorname {lcm} (a,b)=a\cdot b.$
• $\operatorname {lcm} (a_{1}^{n},a_{2}^{n},...,a_{k}^{n})=(\operatorname {lcm} (a_{1},a_{2},...,a_{k}))^{n}$ пры $n\geqslant 0.$
• Найменшае агульнае кратнае двух цэлых лікаў m і n з'яўляецца дзельнікам усіх іншых агульных кратных m і n. Больш таго, мноства агульных кратных m і n супадае з мноствам кратных для НАК(m, n).
• Асімптотыкі для $\operatorname {lcm} (1,2,\ldots ,n)$ можна выразіць праз некаторыя тэарэтыка-лікавыя функцыі.
  • Функцыя Чабышова $\psi (x)=\ln \operatorname {lcm} (1,2,\ldots ,\lfloor x\rfloor ).$
  • $\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).
  • $\operatorname {lcm} (1,2,\ldots ,n)\sim e^{n+o(1)}$, што вынікае з закона размеркавання простых лікаў.

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

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

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

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

2. Няхай вядома кананічнае раскладанне абодвух лікаў на простыя множнікі:

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

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

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

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

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

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

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

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

Вылічэнне найменшага агульнага кратнага некалькіх лікаў можна звесці да некалькіх паслядоўных вылічэнняў НАК ад двух лікаў:

• $\operatorname {lcm} (a,b,c)=\operatorname {lcm} (\operatorname {lcm} (a,b),c);$
• $\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 (нявызн.). MathWorld.