ГлавнаяНаименьшее общее кратное ( H O K {displaystyle mathrm {HOK} } ) двух целых чисел m {displaystyle m} и n {displaystyle n} есть наименьшее натуральное число, которое делится на m {displaystyle m} и n {displaystyle n} без остатка, то есть кратно им обоим. Обозначается одним из следующих способов:
- H O K ( m , n ) {displaystyle mathrm {HOK} (m,n)} ;
- [ m , n ] {displaystyle [m,n]} ;
- L C M ( m , n ) {displaystyle mathrm {LCM} (m,n)} или l c m ( m , n ) {displaystyle mathrm {lcm} (m,n)} (от англ. least common multiple).
Пример: H O K ( 16 , 20 ) = 80 {displaystyle mathrm {HOK} (16,20)=80} .
Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.
Одно из наиболее частых применений H O K {displaystyle mathrm {HOK} } — приведение дробей к общему знаменателю.
Свойства
- Коммутативность: l c m ( a , b ) = l c m ( b , a ) {displaystyle mathrm {lcm} (a,b)=mathrm {lcm} (b,a)} .
- Ассоциативность: l c m ( a , l c m ( b , c ) ) = l c m ( l c m ( a , b ) , c ) {displaystyle mathrm {lcm} (a,mathrm {lcm} (b,c))=mathrm {lcm} (mathrm {lcm} (a,b),c)} .
- Связь с наибольшим общим делителем g c d ( a , b ) {displaystyle mathrm {gcd} (a,b)} : lcm ( a , b ) = | a ⋅ b | gcd ( a , b ) . {displaystyle operatorname {lcm} (a,b)={frac {|acdot b|}{operatorname {gcd} (a,b)}}.}
- В частности, если a {displaystyle a} и b {displaystyle b} — взаимно-простые числа, то lcm ( a , b ) = a ⋅ b . {displaystyle operatorname {lcm} (a,b)=acdot b.}
- lcm ( a 1 n , a 2 n , . . . , a k n ) = ( lcm ( a 1 , a 2 , . . . , a k ) ) n {displaystyle operatorname {lcm} (a_{1}^{n},a_{2}^{n},...,a_{k}^{n})=(operatorname {lcm} (a_{1},a_{2},...,a_{k}))^{n}} при n ⩾ 0. {displaystyle ngeqslant 0.}
- Наименьшее общее кратное двух целых чисел m {displaystyle m} и n {displaystyle n} является делителем всех других общих кратных m {displaystyle m} и n {displaystyle n} . Более того, множество общих кратных m {displaystyle m} , n {displaystyle n} совпадает с множеством кратных для H O K ( m , n ) {displaystyle mathrm {HOK} (m,n)} .
- Асимптотики для lcm ( 1 , 2 , … , n ) {displaystyle operatorname {lcm} (1,2,ldots ,n)} могут быть выражены через некоторые теоретико-числовые функции. Так:
- функция Чебышёва ψ ( x ) = ln lcm ( 1 , 2 , … , ⌊ x ⌋ ) ; {displaystyle psi (x)=ln operatorname {lcm} (1,2,ldots ,lfloor x floor );}
- lcm ( 1 , 2 , … , n ) ⩽ g ( n ( n + 1 ) 2 ) ∼ e n ( n + 1 ) 2 ln n ( n + 1 ) 2 , {displaystyle operatorname {lcm} (1,2,ldots ,n)leqslant gleft({frac {n(n+1)}{2}} ight)sim e^{sqrt {{frac {n(n+1)}{2}}ln {frac {n(n+1)}{2}}}},} что следует из определения и свойств функции Ландау g ( n ) {displaystyle g(n)} ;
- lcm ( 1 , 2 , … , n ) ∼ e n + o ( 1 ) , {displaystyle operatorname {lcm} (1,2,ldots ,n)sim e^{n+o(1)},} что следует из закона распределения простых чисел.
Нахождение НОК
H O K ( a , b ) {displaystyle mathrm {HOK} (a,b)} можно вычислить несколькими способами.
1. Если известен наибольший общий делитель, можно использовать его связь с H O K {displaystyle mathrm {HOK} } :
lcm ( a , b ) = | a ⋅ b | gcd ( a , b ) {displaystyle operatorname {lcm} (a,b)={frac {|acdot b|}{operatorname {gcd} (a,b)}}}2. Пусть известно каноническое разложение обоих чисел на простые множители:
a = p 1 d 1 ⋅ ⋯ ⋅ p k d k , {displaystyle a=p_{1}^{d_{1}}cdot dots cdot p_{k}^{d_{k}},} b = p 1 e 1 ⋅ ⋯ ⋅ p k e k , {displaystyle b=p_{1}^{e_{1}}cdot dots cdot p_{k}^{e_{k}},}где p 1 , … , p k {displaystyle p_{1},dots ,p_{k}} — различные простые числа, а d 1 , … , d k {displaystyle d_{1},dots ,d_{k}} и e 1 , … , e k {displaystyle e_{1},dots ,e_{k}} — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда H O K ( a , b ) {displaystyle mathrm {HOK} (a,b)} вычисляется по формуле:
lcm ( a , b ) = p 1 max ( d 1 , e 1 ) ⋅ ⋯ ⋅ p k max ( d k , e k ) . {displaystyle operatorname {lcm} (a,b)=p_{1}^{max(d_{1},e_{1})}cdot dots cdot p_{k}^{max(d_{k},e_{k})}.}Другими словами, разложение H O K {displaystyle mathrm {HOK} } содержит все простые множители, входящие хотя бы в одно из разложений чисел a , b {displaystyle a,b} , причём из показателей степени этого множителя берётся наибольший. Пример для бóльшего количества чисел:
56 = 2 3 ⋅ 3 0 ⋅ 7 1 {displaystyle 56;,;,=2^{3}cdot 3^{0}cdot 7^{1}} 9 = 2 0 ⋅ 3 2 ⋅ 7 0 {displaystyle 9;,;,=2^{0}cdot 3^{2}cdot 7^{0}} 21 = 2 0 ⋅ 3 1 ⋅ 7 1 . {displaystyle 21;,=2^{0}cdot 3^{1}cdot 7^{1}.} lcm ( 56 , 9 , 21 ) = 2 3 ⋅ 3 2 ⋅ 7 1 = 8 ⋅ 9 ⋅ 7 = 504. {displaystyle operatorname {lcm} (56,9,21)=2^{3}cdot 3^{2}cdot 7^{1}=8cdot 9cdot 7=504.}Вычисление наименьшего общего кратного нескольких чисел может быть также сведено к нескольким последовательным вычислениям H O K {displaystyle mathrm {HOK} } от двух чисел:
- lcm ( a , b , c ) = lcm ( lcm ( a , b ) , c ) ; {displaystyle operatorname {lcm} (a,b,c)=operatorname {lcm} (operatorname {lcm} (a,b),c);}
- lcm ( a 1 , a 2 , … , a n ) = lcm ( lcm ( a 1 , a 2 , … , a n − 1 ) , a n ) . {displaystyle operatorname {lcm} (a_{1},a_{2},ldots ,a_{n})=operatorname {lcm} (operatorname {lcm} (a_{1},a_{2},ldots ,a_{n-1}),a_{n}).}