Наименьшее общее кратное
Поделись знанием:
– Вишь, их, как плотину, прорвало, – безнадежно останавливаясь, говорил казак. – Много ль вас еще там?
– Мелион без одного! – подмигивая говорил близко проходивший в прорванной шинели веселый солдат и скрывался; за ним проходил другой, старый солдат.
– Как он (он – неприятель) таперича по мосту примется зажаривать, – говорил мрачно старый солдат, обращаясь к товарищу, – забудешь чесаться.
И солдат проходил. За ним другой солдат ехал на повозке.
– Куда, чорт, подвертки запихал? – говорил денщик, бегом следуя за повозкой и шаря в задке.
И этот проходил с повозкой. За этим шли веселые и, видимо, выпившие солдаты.
– Как он его, милый человек, полыхнет прикладом то в самые зубы… – радостно говорил один солдат в высоко подоткнутой шинели, широко размахивая рукой.
– То то оно, сладкая ветчина то. – отвечал другой с хохотом.
И они прошли, так что Несвицкий не узнал, кого ударили в зубы и к чему относилась ветчина.
– Эк торопятся, что он холодную пустил, так и думаешь, всех перебьют. – говорил унтер офицер сердито и укоризненно.
– Как оно пролетит мимо меня, дяденька, ядро то, – говорил, едва удерживаясь от смеха, с огромным ртом молодой солдат, – я так и обмер. Право, ей Богу, так испужался, беда! – говорил этот солдат, как будто хвастаясь тем, что он испугался. И этот проходил. За ним следовала повозка, непохожая на все проезжавшие до сих пор. Это был немецкий форшпан на паре, нагруженный, казалось, целым домом; за форшпаном, который вез немец, привязана была красивая, пестрая, с огромным вымем, корова. На перинах сидела женщина с грудным ребенком, старуха и молодая, багроворумяная, здоровая девушка немка. Видно, по особому разрешению были пропущены эти выселявшиеся жители. Глаза всех солдат обратились на женщин, и, пока проезжала повозка, двигаясь шаг за шагом, и, все замечания солдат относились только к двум женщинам. На всех лицах была почти одна и та же улыбка непристойных мыслей об этой женщине.
Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка. Обозначается одним из следующих способов:
- НОК(m, n);
- [m, n];
- lcm(m, n) (от англ. Least Common Multiple).
Пример: НОК(16, 20) = 80.
Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.
Одно из наиболее частых применений НОК — приведение дробей к общему знаменателю.
Содержание
Свойства
- Коммутативность: <math>\operatorname{lcm}(a, b) = \operatorname{lcm}(b, a).</math>
- Ассоциативность: <math>\operatorname{lcm}(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\operatorname{lcm}(a, b), c).</math>
- Связь с наибольшим общим делителем gcd(a,b):
- <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>m</math>, <math>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>. Это следует из определения и свойств функции Ландау g(n).
- <math>\operatorname{lcm} (1, 2, \ldots, n)\sim e^{n+o(1)}</math>, что следует из закона распределения простых чисел.
Нахождение НОК
НОК(a, b) можно вычислить несколькими способами.
1. Если известен наибольший общий делитель, можно использовать его связь с НОК:
- <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> — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОК(a,b) вычисляется по формуле:
- <math>[a,b]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.</math>
Другими словами, разложение НОК содержит все простые множители, входящие хотя бы в одно из разложений чисел a, b, причём из двух показателей степени этого множителя берётся наибольший. Пример:
- <math>8\; \, \; \,= 2^3 \cdot 3^0 \cdot 5^0 \cdot 7^0</math>
- <math>9\; \, \; \,= 2^0 \cdot 3^2 \cdot 5^0 \cdot 7^0</math>
- <math>21\; \,= 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1.</math>
- <math>\operatorname{lcm}(8,9,21) = 2^3 \cdot 3^2 \cdot 5^0 \cdot 7^1 = 8 \cdot 9 \cdot 1 \cdot 7 = 504.</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>
См. также
Напишите отзыв о статье "Наименьшее общее кратное"
Литература
- Виноградов И. М. [math.ru/lib/book/djvu/vinogradov.djvu Основы теории чисел]. — М.-Л.: ГИТТЛ, 1952. — 180 с.
Ссылки
- Weisstein, Eric W. [mathworld.wolfram.com/LeastCommonMultiple.html Least Common Multiple] (англ.) на сайте Wolfram MathWorld.
Отрывок, характеризующий Наименьшее общее кратное
Но фурштат, не обращая внимания на наименование генерала, кричал на солдат, запружавших ему дорогу: – Эй! землячки! держись влево, постой! – Но землячки, теснясь плечо с плечом, цепляясь штыками и не прерываясь, двигались по мосту одною сплошною массой. Поглядев за перила вниз, князь Несвицкий видел быстрые, шумные, невысокие волны Энса, которые, сливаясь, рябея и загибаясь около свай моста, перегоняли одна другую. Поглядев на мост, он видел столь же однообразные живые волны солдат, кутасы, кивера с чехлами, ранцы, штыки, длинные ружья и из под киверов лица с широкими скулами, ввалившимися щеками и беззаботно усталыми выражениями и движущиеся ноги по натасканной на доски моста липкой грязи. Иногда между однообразными волнами солдат, как взбрызг белой пены в волнах Энса, протискивался между солдатами офицер в плаще, с своею отличною от солдат физиономией; иногда, как щепка, вьющаяся по реке, уносился по мосту волнами пехоты пеший гусар, денщик или житель; иногда, как бревно, плывущее по реке, окруженная со всех сторон, проплывала по мосту ротная или офицерская, наложенная доверху и прикрытая кожами, повозка.– Вишь, их, как плотину, прорвало, – безнадежно останавливаясь, говорил казак. – Много ль вас еще там?
– Мелион без одного! – подмигивая говорил близко проходивший в прорванной шинели веселый солдат и скрывался; за ним проходил другой, старый солдат.
– Как он (он – неприятель) таперича по мосту примется зажаривать, – говорил мрачно старый солдат, обращаясь к товарищу, – забудешь чесаться.
И солдат проходил. За ним другой солдат ехал на повозке.
– Куда, чорт, подвертки запихал? – говорил денщик, бегом следуя за повозкой и шаря в задке.
И этот проходил с повозкой. За этим шли веселые и, видимо, выпившие солдаты.
– Как он его, милый человек, полыхнет прикладом то в самые зубы… – радостно говорил один солдат в высоко подоткнутой шинели, широко размахивая рукой.
– То то оно, сладкая ветчина то. – отвечал другой с хохотом.
И они прошли, так что Несвицкий не узнал, кого ударили в зубы и к чему относилась ветчина.
– Эк торопятся, что он холодную пустил, так и думаешь, всех перебьют. – говорил унтер офицер сердито и укоризненно.
– Как оно пролетит мимо меня, дяденька, ядро то, – говорил, едва удерживаясь от смеха, с огромным ртом молодой солдат, – я так и обмер. Право, ей Богу, так испужался, беда! – говорил этот солдат, как будто хвастаясь тем, что он испугался. И этот проходил. За ним следовала повозка, непохожая на все проезжавшие до сих пор. Это был немецкий форшпан на паре, нагруженный, казалось, целым домом; за форшпаном, который вез немец, привязана была красивая, пестрая, с огромным вымем, корова. На перинах сидела женщина с грудным ребенком, старуха и молодая, багроворумяная, здоровая девушка немка. Видно, по особому разрешению были пропущены эти выселявшиеся жители. Глаза всех солдат обратились на женщин, и, пока проезжала повозка, двигаясь шаг за шагом, и, все замечания солдат относились только к двум женщинам. На всех лицах была почти одна и та же улыбка непристойных мыслей об этой женщине.
