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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

  • НОК(m, n);
  • [m, n];
  • lcm(mn)    (от англ. Least Common Multiple).

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

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

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

Свойства[править | править вики-текст]

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

Нахождение НОК[править | править вики-текст]

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

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

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

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

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]