Открыть главное меню

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

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

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

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

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

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

СвойстваПравить

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

Нахождение НОКПравить

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

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

 

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

 
 

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

 

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

 
 
 
 

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

  •  
  •  

См. такжеПравить

ЛитератураПравить

СсылкиПравить