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

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

  • НОК(m, n);
  • [m, n];
  • lcm(mn)    (от ).

 Пример: НОК(16, 20) = 80.
 Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.
 Одно из наиболее частых применений НОК — приведение дробей к общему знаменателю.

Свойства



  • Коммутативность: lcm(a,b)=lcm(b,a).
  • Ассоциативность: lcm(a,lcm(b,c))=lcm(lcm(a,b),c).
  • Связь с наибольшим общим делителем gcd(a,b):
      \{operatorname\{lcm\}(a,b)=\{frac\{
  • В частности, если a и b — взаимно-простые числа, то lcm(a,b)=ab.
  • lcm(a1n,a2n,...,akn)=(lcm(a1,a2,...,ak))n при n0.
  • Наименьшее общее кратное двух целых чисел m и n является делителем всех других общих кратных m и n. Более того, множество общих кратных m, n совпадает с множеством кратных для НОК(m, n).
  • Асимптотики для lcm(1,2,,n) могут быть выражены через некоторые теоретико-числовые функции. Так:
    • функция Чебышёва ψ(x)=lnlcm(1,2,,x);
    • lcm(1,2,,n)g(n(n+1)2)en(n+1)2lnn(n+1)2, что следует из определения и свойств функции Ландау g(n);
    • lcm(1,2,,n)en+o(1), что следует из закона распределения простых чисел.

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


 НОК(a, b) можно вычислить несколькими способами.
 1. Если известен наибольший общий делитель, можно использовать его связь с НОК:
 $$\operatorname{lcm}(a,b)=\frac{|
 2. Пусть известно каноническое разложение обоих чисел на простые множители: :: a=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},$$


b=p1e1pkek,

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


[a,b]=p1max(d1,e1)pkmax(dk,ek).

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

9=20325070

21=20315071.

lcm(8,9,21)=23325071=8917=504.

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

  • lcm(a,b,c)=lcm(lcm(a,b),c);
  • lcm(a1,a2,,an)=lcm(lcm(a1,a2,,an1),an).