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

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

• $\mathrm{H}\mathrm{O}\mathrm{K}(m,n)$;
• $[m,n]$;
• $\mathrm{L}\mathrm{C}\mathrm{M}(m,n)$ или $\mathrm{l}\mathrm{c}\mathrm{m}(m,n)$    (от Шаблон:Lang-en).

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

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

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

Свойства

• Коммутативность: $\mathrm{l}\mathrm{c}\mathrm{m}(a,b)=\mathrm{l}\mathrm{c}\mathrm{m}(b,a)$.
• Ассоциативность: $\mathrm{l}\mathrm{c}\mathrm{m}(a,\mathrm{l}\mathrm{c}\mathrm{m}(b,c))=\mathrm{l}\mathrm{c}\mathrm{m}(\mathrm{l}\mathrm{c}\mathrm{m}(a,b),c)$.
• Связь с наибольшим общим делителем $\mathrm{g}\mathrm{c}\mathrm{d}(a,b)$:

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

• В частности, если $a$ и $b$ — взаимно-простые числа, то $\mathrm{lcm}(a,b)=a\cdot b.$
• $\mathrm{lcm}(a_1^n,a_2^n,\mathrm{...},a_k^n)=(\mathrm{lcm}(a_1,a_2,\mathrm{...},a_k){)}^n$ при $n⩾0.$
• Наименьшее общее кратное двух целых чисел $m$ и $n$ является делителем всех других общих кратных $m$ и $n$. Более того, множество общих кратных $m$, $n$ совпадает с множеством кратных для $\mathrm{H}\mathrm{O}\mathrm{K}(m,n)$.
• Асимптотики для $\mathrm{lcm}(1,2,\dots ,n)$ могут быть выражены через некоторые теоретико-числовые функции. Так:
  • функция Чебышёва $\psi (x)=\ln \mathrm{lcm}(1,2,\dots ,\lfloor x\rfloor );$
  • $\mathrm{lcm}(1,2,\dots ,n)⩽g\left(\frac{n(n+1)}{2}\right)\sim e^{\sqrt{\frac{n(n+1)}{2}\ln \frac{n(n+1)}{2}}},$ что следует из определения и свойств функции Ландау $g(n)$;
  • $\mathrm{lcm}(1,2,\dots ,n)\sim e^{n+o(1)},$ что следует из закона распределения простых чисел.

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

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

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

$\mathrm{lcm}(a,b)=\frac{|a\cdot b|}{\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{H}\mathrm{O}\mathrm{K}(a,b)$ вычисляется по формуле:

$\mathrm{lcm}(a,b)=p_1^{max(d_1,e_1)}\cdot \dots \cdot p_k^{max(d_k,e_k)}.$

Другими словами, разложение $\mathrm{H}\mathrm{O}\mathrm{K}$ содержит все простые множители, входящие хотя бы в одно из разложений чисел $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.$

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

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

• $\mathrm{lcm}(a,b,c)=\mathrm{lcm}(\mathrm{lcm}(a,b),c);$
• $\mathrm{lcm}(a_1,a_2,\dots ,a_n)=\mathrm{lcm}(\mathrm{lcm}(a_1,a_2,\dots ,a_{n-1}),a_n).$

См. также

• Наибольший общий делитель

Литература

• Шаблон:Книга

Ссылки

• Шаблон:MathWorld