Русская Википедия:Наименьшее общее кратное
Наиме́ньшее о́бщее кра́тное (<math>\mathrm{HOK}</math>) двух целых чисел <math>m</math> и <math>n</math> есть наименьшее натуральное число, которое делится на <math>m</math> и <math>n</math> без остатка, то есть кратно им обоим. Обозначается одним из следующих способов:
- <math>\mathrm{HOK}(m, n)</math>;
- <math>[m, n]</math>;
- <math>\mathrm{LCM}(m, n)</math> или <math>\mathrm{lcm}(m, n)</math> (от Шаблон:Lang-en).
Пример: <math>\mathrm{HOK}(16, 20) = 80</math>.
Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.
Одно из наиболее частых применений <math>\mathrm{HOK}</math> — приведение дробей к общему знаменателю.
Свойства
- Коммутативность: <math>\mathrm{lcm}(a, b) = \mathrm{lcm}(b, a)</math>.
- Ассоциативность: <math>\mathrm{lcm}(a, \mathrm{lcm}(b, c)) = \mathrm{lcm}(\mathrm{lcm}(a, b), c)</math>.
- Связь с наибольшим общим делителем <math>\mathrm{gcd}(a,b)</math>:
- <math>\operatorname{lcm}(a,b)=\frac{|a \cdot b|}{\operatorname{gcd}(a,b)}.</math>
- В частности, если <math>a</math> и <math>b</math> — взаимно-простые числа, то <math>\operatorname{lcm}(a, b) = a \cdot b.</math>
- <math>\operatorname{lcm}(a_1^n, a_2^n, ..., a_k^n) = (\operatorname{lcm}(a_1, a_2, ..., a_k))^n</math> при <math>n \geqslant 0 .</math>
- Наименьшее общее кратное двух целых чисел <math>m</math> и <math>n</math> является делителем всех других общих кратных <math>m</math> и <math>n</math>. Более того, множество общих кратных <math>m</math>, <math>n</math> совпадает с множеством кратных для <math>\mathrm{HOK}(m, n)</math>.
- Асимптотики для <math>\operatorname{lcm}(1, 2, \ldots, n)</math> могут быть выражены через некоторые теоретико-числовые функции. Так:
- функция Чебышёва <math>\psi(x)=\ln \operatorname{lcm}(1, 2,\ldots, \lfloor x\rfloor) ;</math>
- <math>\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}}} ,</math> что следует из определения и свойств функции Ландау <math>g(n)</math>;
- <math>\operatorname{lcm} (1, 2, \ldots, n)\sim e^{n+o(1)} ,</math> что следует из закона распределения простых чисел.
Нахождение НОК
<math>\mathrm{HOK}(a, b)</math> можно вычислить несколькими способами.
1. Если известен наибольший общий делитель, можно использовать его связь с <math>\mathrm{HOK}</math>:
- <math>\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}</math>
2. Пусть известно каноническое разложение обоих чисел на простые множители:
- <math>a=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},</math>
- <math>b=p_1^{e_1}\cdot \dots \cdot p_k^{e_k},</math>
где <math>p_1,\dots,p_k</math> — различные простые числа, а <math>d_1,\dots,d_k</math> и <math>e_1,\dots,e_k</math> — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда <math>\mathrm{HOK}(a, b)</math> вычисляется по формуле:
- <math>\operatorname{lcm}(a,b)=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.</math>
Другими словами, разложение <math>\mathrm{HOK}</math> содержит все простые множители, входящие хотя бы в одно из разложений чисел <math>a, b</math>, причём из показателей степени этого множителя берётся наибольший. Пример для бóльшего количества чисел:
- <math>56\; \, \; \,= 2^3 \cdot 3^0 \cdot 7^1</math>
- <math>9\; \, \; \,= 2^0 \cdot 3^2 \cdot 7^0</math>
- <math>21\; \,= 2^0 \cdot 3^1 \cdot 7^1.</math>
- <math>\operatorname{lcm}(56,9,21) = 2^3 \cdot 3^2 \cdot 7^1 = 8 \cdot 9 \cdot 7 = 504.</math>
Вычисление наименьшего общего кратного нескольких чисел может быть также сведено к нескольким последовательным вычислениям <math>\mathrm{HOK}</math> от двух чисел:
- <math>\operatorname{lcm}(a, b, c) = \operatorname{lcm}(\operatorname{lcm}(a, b), c);</math>
- <math>\operatorname{lcm}(a_1, a_2, \ldots, a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1, a_2, \ldots, a_{n-1}), a_n).</math>
См. также
Литература
Ссылки
