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

• НОК(m, n);
• [m, n];
• lcm(m, n)    (от англ. least common multiple).

Пример: НОК(16, 20) = 80.

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

Одно из наиболее частых применений НОК — приведение дробей к общему знаменателю.

Свойства

• Коммутативность:
• Ассоциативность:
• Связь с наибольшим общим делителем gcd(a,b):

• В частности, если и  — взаимно-простые числа, то:
• при
• Наименьшее общее кратное двух целых чисел и является делителем всех других общих кратных и . Более того, множество общих кратных m, n совпадает с множеством кратных для НОК(m, n).
• Асимптотики для могут быть выражены через некоторые теоретико-числовые функции. Так, функция Чебышёва . А также:
  • . Это следует из определения и свойств функции Ландау g(n).
  • , что следует из закона распределения простых чисел.

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

НОК(a, b) можно вычислить несколькими способами.

1. Если известен наибольший общий делитель, можно использовать его связь с НОК:

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

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОК(a,b) вычисляется по формуле:

Другими словами, разложение НОК содержит все простые множители, входящие хотя бы в одно из разложений чисел a, b, причём из двух показателей степени этого множителя берётся наибольший. Пример:

Вычисление наименьшего общего кратного нескольких чисел может быть сведено к нескольким последовательным вычислениям НОК от двух чисел:

См. также

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

Литература

• Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Ссылки

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