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

Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел 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 (англ.) на сайте Wolfram MathWorld.