WikiSort.ru - Не сортированное

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

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

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

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

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

Свойства

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

  ${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.}$

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

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

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

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

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}}$

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

${\displaystyle a=p_{1}^{d_{1}}\cdot \dots \cdot p_{k}^{d_{k}},}$

${\displaystyle b=p_{1}^{e_{1}}\cdot \dots \cdot p_{k}^{e_{k}},}$

где ${\displaystyle p_{1},\dots ,p_{k}}$ — различные простые числа, а ${\displaystyle d_{1},\dots ,d_{k}}$ и ${\displaystyle e_{1},\dots ,e_{k}}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОК(a,b) вычисляется по формуле:

${\displaystyle [a,b]=p_{1}^{\max(d_{1},e_{1})}\cdot \dots \cdot p_{k}^{\max(d_{k},e_{k})}.}$

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

${\displaystyle 8\;\,\;\,=2^{3}\cdot 3^{0}\cdot 5^{0}\cdot 7^{0}}$

${\displaystyle 9\;\,\;\,=2^{0}\cdot 3^{2}\cdot 5^{0}\cdot 7^{0}}$

${\displaystyle 21\;\,=2^{0}\cdot 3^{1}\cdot 5^{0}\cdot 7^{1}.}$

${\displaystyle \operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 5^{0}\cdot 7^{1}=8\cdot 9\cdot 1\cdot 7=504.}$

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

• ${\displaystyle \operatorname {lcm} (a,b,c)=\operatorname {lcm} (\operatorname {lcm} (a,b),c);}$
• ${\displaystyle \operatorname {lcm} (a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{n-1}),a_{n}).}$

См. также

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

Литература

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

Ссылки

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