Меню Главная Случайная статья Настройки Наименьшее общее кратное Материал из https://ru.wikipedia.org Наименьшее общее кратное (${\displaystyle \mathrm {HOK} }$) двух целых чисел ${\displaystyle m}$ и ${\displaystyle n}$ есть наименьшее натуральное число, которое делится на ${\displaystyle m}$ и ${\displaystyle n}$ без остатка, то есть кратно им обоим. Обозначается одним из следующих способов: ${\displaystyle \mathrm {HOK} (m,n)}$; ${\displaystyle [m,n]}$; ${\displaystyle \mathrm {LCM} (m,n)}$ или ${\displaystyle \mathrm {lcm} (m,n)}$    (от англ. least common multiple). Пример: ${\displaystyle \mathrm {HOK} (16,20)=80}$. Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел. Одно из наиболее частых применений ${\displaystyle \mathrm {HOK} }$ — приведение дробей к общему знаменателю. Содержание 1 Свойства 2 Нахождение НОК 3 См. также 4 Литература 5 Ссылки Свойства Коммутативность: ${\displaystyle \mathrm {lcm} (a,b)=\mathrm {lcm} (b,a)}$. Ассоциативность: ${\displaystyle \mathrm {lcm} (a,\mathrm {lcm} (b,c))=\mathrm {lcm} (\mathrm {lcm} (a,b),c)}$. Связь с наибольшим общим делителем ${\displaystyle \mathrm {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 \mathrm {HOK} (m,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}}}},}$ что следует из определения и свойств функции Ландау ${\displaystyle g(n)}$; ${\displaystyle \operatorname {lcm} (1,2,\ldots ,n)\sim e^{n+o(1)},}$ что следует из закона распределения простых чисел. Нахождение НОК ${\displaystyle \mathrm {HOK} (a,b)}$ можно вычислить несколькими способами. 1. Если известен наибольший общий делитель, можно использовать его связь с ${\displaystyle \mathrm {HOK} }$: ${\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}}$ — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда ${\displaystyle \mathrm {HOK} (a,b)}$ вычисляется по формуле: ${\displaystyle \operatorname {lcm} (a,b)=p_{1}^{\max(d_{1},e_{1})}\cdot \dots \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 \operatorname {lcm} (56,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$ Вычисление наименьшего общего кратного нескольких чисел может быть также сведено к нескольким последовательным вычислениям ${\displaystyle \mathrm {HOK} }$ от двух чисел: ${\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.