Наименьшее общее кратное

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

  • НОК(mn);
  • [mn];
  • lcm(mn)    (от англ. Least Common Multiple).

Пример: НОК(16, 20) = 80.

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

Одно из наиболее частых применений НОК — приведение дробей к общему знаменателю.

Свойства[править | править вики-текст]

Нахождение НОК[править | править вики-текст]

НОК(a, b) можно вычислить несколькими способами.

1. Если известен наибольший общий делитель, можно использовать его связь с НОК:

\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}

2. Пусть известно каноническое разложение обоих чисел на простые множители:

a=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},
b=p_1^{e_1}\cdot \dots \cdot p_k^{e_k},

где p_1,\dots,p_k — различные простые числа, а d_1,\dots,d_k и e_1,\dots,e_k — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОК(a,b) вычисляется по формуле:

[a,b]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.

Другими словами, разложение НОК содержит все простые множители, входящие хотя бы в одно из разложений чисел a, b, причём из двух показателей степени этого множителя берётся наибольший. Пример:

8\; \, \; \,= 2^3 \cdot 3^0 \cdot 5^0 \cdot 7^0 \,\!
9\; \, \; \,= 2^0 \cdot 3^2 \cdot 5^0 \cdot 7^0 \,\!
21\; \,= 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1. \,\!
\operatorname{lcm}(8,9,21) = 2^3 \cdot 3^2 \cdot 5^0 \cdot 7^1 = 8 \cdot 9 \cdot 1 \cdot 7 = 504. \,\!

Вычисление наименьшего общего кратного нескольких чисел может быть сведено к нескольким последовательным вычислениям НОК от двух чисел:

  • \operatorname{lcm}(a, b, c) = \operatorname{lcm}(\operatorname{lcm}(a, b), c);
  • \operatorname{lcm}(a_1, a_2, \ldots, a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1, a_2, \ldots, a_{n-1}), a_n).

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]