Найменше спільне кратне

Матеріал з Вікіпедії — вільної енциклопедії.

Перейти до: навігація, пошук

Найменше спільне кратне (НСК) двох цілих чисел a, b називаємо найменше натуральне число, яке є кратним обох цих чисел. Позначаємо НСК(a, b), в англомовній літературі LCM(a, b). Отже НСК(a, b) є найменшим натуральним числом, яке ділиться без залишку на обидва числа a, b. Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.

[ред.] Властивості

  • НСК(a, b)= НСК(b, a) (перестановка аргументів не змінює НСК).
  • НСК(a, b, c, d) = НСК(НСК(a, b), НСК(c, d) )

[ред.] Обчислення НСК методом розкладу на прості множники

Нехай розклад чисел на прості множники:

a=2^{q_2}\cdot 3^{q_3}\cdot \dots \cdot p_k^{q_{p_k}}
b=2^{r_2}\cdot 3^{r_3}\cdot \dots \cdot p_k^{r_{p_k}}

Тоді

НСД(a,b)= 2^{\max(q_2;r_2)} \cdot 3^{\max(q_3;r_3)} \cdot \dots \cdot p_k^{\max(q_{p_k};q_{p_k})}

[ред.] Приклад

Визначимо НСК(840,396). Розклад на прості множники:

840 = 2^3 \cdot 3 \cdot 5 \cdot 7
396 = 2^2 \cdot 3^2 \cdot 11 ,

або, подаючи для наглядності нульові степені,

840 = 2^3 \cdot 3^1 \cdot 5^1 \cdot 7^1 \cdot 11^0
396 = 2^2 \cdot 3^2 \cdot 5^0 \cdot 7^0 \cdot 11^1 ,

Отже,

НСК(840,396)=2^3\cdot 3^2\cdot 5^1\cdot 7^1 \cdot 11^1=27720

НСК можна теж обчислити за допомогою рівності НСК(a, b) =|ab|/НСД(a, b), використавши для обчислення НСД ефективний алгоритм Евкліда

Отримано з http://uk.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B9%D0%BC%D0%B5%D0%BD%D1%88%D0%B5_%D1%81%D0%BF%D1%96%D0%BB%D1%8C%D0%BD%D0%B5_%D0%BA%D1%80%D0%B0%D1%82%D0%BD%D0%B5
Особисті інструменти