Наименьшее общее кратное

Наиме́ньшее о́бщее кра́тное ($\mathrm {HOK}$) двух целых чисел $m$ и $n$ есть наименьшее натуральное число, которое делится на $m$ и $n$ без остатка, то есть кратно им обоим. Обозначается одним из следующих способов:

• $\mathrm {HOK} (m,n)$;
• $[m,n]$;
• $\mathrm {LCM} (m,n)$ или $\mathrm {lcm} (m,n)$    (от англ. least common multiple).

Пример: $\mathrm {HOK} (16,20)=80$.

Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.

Одно из наиболее частых применений $\mathrm {HOK}$ — приведение дробей к общему знаменателю.

Свойства

• Коммутативность: $\mathrm {lcm} (a,b)=\mathrm {lcm} (b,a)$.
• Ассоциативность: $\mathrm {lcm} (a,\mathrm {lcm} (b,c))=\mathrm {lcm} (\mathrm {lcm} (a,b),c)$.
• Связь с наибольшим общим делителем $\mathrm {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$ совпадает с множеством кратных для $\mathrm {HOK} (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)},$ что следует из закона распределения простых чисел.

Нахождение НОК

$\mathrm {HOK} (a,b)$ можно вычислить несколькими способами.

1. Если известен наибольший общий делитель, можно использовать его связь с $\mathrm {HOK}$:

$\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}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда $\mathrm {HOK} (a,b)$ вычисляется по формуле:

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

Другими словами, разложение $\mathrm {HOK}$ содержит все простые множители, входящие хотя бы в одно из разложений чисел $a,b$, причём из показателей степени этого множителя берётся наибольший. Пример для бóльшего количества чисел:

$56\;\,\;\,=2^{3}\cdot 3^{0}\cdot 7^{1}$

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

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

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

Вычисление наименьшего общего кратного нескольких чисел может быть также сведено к нескольким последовательным вычислениям $\mathrm {HOK}$ от двух чисел:

• $\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 (англ.) на сайте Wolfram MathWorld.