ru.wikipedia.org

Наименьшее общее кратное — Википедия

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

Пример: {\displaystyle \mathrm {HOK} (16,20)=80}.

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

Одно из наиболее частых применений {\displaystyle \mathrm {HOK} } — приведение дробей к общему знаменателю.

{\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}).}