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

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

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

Пример: [math]\displaystyle{ \mathrm{HOK}(16, 20) = 80 }[/math].

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

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

Свойства

• Коммутативность: [math]\displaystyle{ \mathrm{lcm}(a, b) = \mathrm{lcm}(b, a) }[/math].
• Ассоциативность: [math]\displaystyle{ \mathrm{lcm}(a, \mathrm{lcm}(b, c)) = \mathrm{lcm}(\mathrm{lcm}(a, b), c) }[/math].
• Связь с наибольшим общим делителем [math]\displaystyle{ \mathrm{gcd}(a,b) }[/math]:

  [math]\displaystyle{ \operatorname{lcm}(a,b)=\frac{|a \cdot b|}{\operatorname{gcd}(a,b)}. }[/math]

• В частности, если [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — взаимно-простые числа, то [math]\displaystyle{ \operatorname{lcm}(a, b) = a \cdot b. }[/math]
• [math]\displaystyle{ \operatorname{lcm}(a_1^n, a_2^n, ..., a_k^n) = (\operatorname{lcm}(a_1, a_2, ..., a_k))^n }[/math] при [math]\displaystyle{ n \geqslant 0 . }[/math]
• Наименьшее общее кратное двух целых чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] является делителем всех других общих кратных [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math]. Более того, множество общих кратных [math]\displaystyle{ m }[/math], [math]\displaystyle{ n }[/math] совпадает с множеством кратных для [math]\displaystyle{ \mathrm{HOK}(m, n) }[/math].
• Асимптотики для [math]\displaystyle{ \operatorname{lcm}(1, 2, \ldots, n) }[/math] могут быть выражены через некоторые теоретико-числовые функции. Так:
  • функция Чебышёва [math]\displaystyle{ \psi(x)=\ln \operatorname{lcm}(1, 2,\ldots, \lfloor x\rfloor) ; }[/math]
  • [math]\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}}} , }[/math] что следует из определения и свойств функции Ландау [math]\displaystyle{ g(n) }[/math];
  • [math]\displaystyle{ \operatorname{lcm} (1, 2, \ldots, n)\sim e^{n+o(1)} , }[/math] что следует из закона распределения простых чисел.

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

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

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

[math]\displaystyle{ \operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)} }[/math]

2. Пусть известно каноническое разложение обоих чисел на простые множители:

[math]\displaystyle{ a=p_1^{d_1}\cdot\dots\cdot p_k^{d_k}, }[/math]

[math]\displaystyle{ b=p_1^{e_1}\cdot \dots \cdot p_k^{e_k}, }[/math]

где [math]\displaystyle{ p_1,\dots,p_k }[/math] — различные простые числа, а [math]\displaystyle{ d_1,\dots,d_k }[/math] и [math]\displaystyle{ e_1,\dots,e_k }[/math] — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда [math]\displaystyle{ \mathrm{HOK}(a, b) }[/math] вычисляется по формуле:

[math]\displaystyle{ \operatorname{lcm}(a,b)=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}. }[/math]

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

[math]\displaystyle{ 56\; \, \; \,= 2^3 \cdot 3^0 \cdot 7^1 }[/math]

[math]\displaystyle{ 9\; \, \; \,= 2^0 \cdot 3^2 \cdot 7^0 }[/math]

[math]\displaystyle{ 21\; \,= 2^0 \cdot 3^1 \cdot 7^1. }[/math]

[math]\displaystyle{ \operatorname{lcm}(56,9,21) = 2^3 \cdot 3^2 \cdot 7^1 = 8 \cdot 9 \cdot 7 = 504. }[/math]

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

• [math]\displaystyle{ \operatorname{lcm}(a, b, c) = \operatorname{lcm}(\operatorname{lcm}(a, b), c); }[/math]
• [math]\displaystyle{ \operatorname{lcm}(a_1, a_2, \ldots, a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1, a_2, \ldots, a_{n-1}), a_n). }[/math]

См. также

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

Литература

• Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.

Ссылки

• Weisstein, Eric W. Least Common Multiple (англ.) на сайте Wolfram MathWorld.