Калькулятор НСД та НСК
Найбільший спільний дільник і найменше спільне кратне
Часті запитання
НСД (найбільший спільний дільник) — найбільше число, яке ділить усі задані числа без остачі. Наприклад, НСД(12, 18) = 6. Знаходять за алгоритмом Евкліда: НСД(a, b) = НСД(b, a mod b), поки b ≠ 0.
НСК (найменше спільне кратне) — найменше число, яке ділиться на всі задані числа. Формула: НСК(a, b) = a × b / НСД(a, b). Наприклад, НСК(4, 6) = 4×6/НСД(4,6) = 24/2 = 12.
НСД використовується для скорочення дробів до найменшого вигляду: 12/18 = 12/НСД(12,18) / 18/НСД(12,18) = 2/3. НСК використовується для додавання дробів з різними знаменниками.
Так. НСД(a, b, c) = НСД(НСД(a, b), c). Послідовно знаходять НСД двох чисел, потім результат і наступне число. Аналогічно для НСК: НСК(a, b, c) = НСК(НСК(a, b), c).
Алгоритм Евкліда для НСД
Алгоритм Евкліда: НСД(a, b): якщо b = 0, то НСД = a; інакше НСД(a, b) = НСД(b, a mod b). Це найефективніший класичний алгоритм знаходження НСД, відомий ще з 300 р. до н.е.
Зв'язок між НСД та НСК: НСД(a, b) × НСК(a, b) = a × b. Тому НСК(a, b) = a × b / НСД(a, b).