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

• Коммутативность: ${\displaystyle {\text{НОК}}(a;b)={\text{НОК}}(b;a)}$.
• Ассоциативность: ${\displaystyle {\text{НОК}}(a;{\text{НОК}}(b;c))={\text{НОК}}({\text{НОК}}(a;b);c)}$
• Связь с наибольшим общим делителем ${\displaystyle {\text{НОД}}(a;b)}$:

  ${\displaystyle {\text{НОК}}(a;b)={\frac {|a\cdot b|}{{\text{НОД}}(a;b)}}.}$

• В частности, если ${\displaystyle a}$ и ${\displaystyle b}$ — взаимно-простые числа, то ${\displaystyle {\text{НОК}}(a;b)=a\cdot b.}$
• Если каждое из чисел ${\displaystyle a_{1},a_{2},\ldots ,a_{k}}$ возвести в одну и ту же неотрицательную степень ${\displaystyle n}$, то их наименьшее общее кратное также возводится в эту степень:

${\displaystyle {\text{НОК}}(a_{1}^{n},a_{2}^{n},\ldots ,a_{k}^{n})=({\text{НОК}}(a_{1},a_{2},\ldots ,a_{k}))^{n}}$ при ${\displaystyle n\geqslant 0}$.

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

${\displaystyle \mathrm {HOK} (a;b)}$ можно вычислить несколькими способами.

1. Если известен Наибольший общий делитель (который может быть найден с помощью алгоритма Евклида), можно использовать его связь с ${\displaystyle \mathrm {HOK} }$:

${\displaystyle {\text{НОК}}(a;b)={\frac {|a\cdot b|}{{\text{НОД}}(a;b)}}}$

Рис. 2. Иллюстрация к определению: кратные чисел 4 и 6; общие кратные (12, 24, …) выделены жёлтым, наименьшее из них — 12.

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}}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда ${\displaystyle \mathrm {HOK} (a;b)}$ вычисляется по формуле:

${\displaystyle {\text{НОК}}(a;b)=p_{1}^{\max(d_{1};e_{1})}\cdot \ldots \cdot p_{k}^{\max(d_{k};e_{k})}.}$

Другими словами, разложение ${\displaystyle \mathrm {HOK} }$ содержит все простые множители, входящие хотя бы в одно из разложений чисел ${\displaystyle a,b}$, причём из показателей степени этого множителя берётся наибольший. Пример для бóльшего количества чисел:

${\displaystyle 56\;\,\;\,=2^{3}\cdot 3^{0}\cdot 7^{1}}$

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

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

${\displaystyle {\text{НОК}}(56;9;21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$

Вычисление наименьшего общего кратного нескольких чисел может быть также сведено к нескольким последовательным вычислениям ${\displaystyle \mathrm {HOK} }$ от двух чисел:

• ${\displaystyle {\text{НОК}}(a;b;c)={\text{НОК}}({\text{НОК}}(a;b);c);}$
• ${\displaystyle {\text{НОК}}(a_{1};a_{2};\ldots ;a_{n})={\text{НОК}}({\text{НОК}}(a_{1};a_{2};\ldots ;a_{n-1});a_{n}).}$