Skvěle, štít %% dosažen
Найбільший спільний дільник
main_page-pexeso
E4WQR kód
Kód / krátká adresa
Zkopírujte kliknutím.
Найбільший спільний дільник
Найбільший спільний дільник (НСД) двох цілих чисел — це найбільше число, яке ділить обидва числа без залишку. Приклади: НСД(18, 24) = 6, НСД(12, 21) = 3, НСД(24, 35) = 1. Поняття найбільшого спільного дільника можна узагальнити на більшу кількість вхідних чисел. Наприклад, НСД(30, 85, 90) = 5. Типовим застосуванням найбільшого спільного дільника є скорочення дробів.
- Якщо найбільший спільний дільник двох чисел дорівнює 1, то їх називають взаємно простими. Наприклад, числа 15 і 32 є взаємно простими.
- Якщо найбільший спільний дільник більше ніж 1, то це спільні числа. Наприклад, числа 20 і 24 мають найбільший спільний дільник 4, тобто вони спільні.
Для малих чисел можна визначити найбільший спільний дільник, просто виписавши всі дільники.
Приклад: НСД (18, 24), розв’язаний переліком дільників
- Дільники числа 18: 1, 2, 3, 6, 9, 18.
- Дільники числа 24: 1, 2, 3, 4, 6, 8, 12, 24.
- Спільні дільники чисел 18 та 24: 1, 2, 3, 6.
- Найбільший спільний дільник — це 6.
Для більших чисел можна визначити найбільший спільний дільник за допомогою розкладу на прості множники. Обидва числа розкладаємо на множники простих чисел, результатом НСД буде добуток простих чисел, що зустрічаються в обох розкладах, піднесених до відповідних найменших показників.
Приклад НСД (18, 24), розв’язаний за допомогою розкладу
- 18 = 2\cdot 3 \cdot 3 = 2\cdot3^2
- 24 = 2 \cdot 2 \cdot 2\cdot 3 = 2^3\cdot 3
- Спільна частина розкладу на прості числа: 2, 3
- \mathit{НСД} (18, 24) = 2\cdot 3 = 6
Приклад НСД (540, 315), розв’язаний за допомогою розкладу
- 540 = 2\cdot 2\cdot3\cdot 3\cdot 3\cdot 5 = 2^2\cdot3^3\cdot 5
- 315 = 3\cdot 3 \cdot 5\cdot 7 = 3^2 \cdot 5\cdot 7
- Спільна частина розкладу на прості числа: 3, 3, 5
- \mathit{НСД} (540, 315) = 3\cdot 3\cdot 5 = 3^2\cdot 5 = 45
Для практичних обчислень використовують інші алгоритми, зокрема алгоритм Евкліда.
Найбільший спільний дільник (střední)
Nyní se opakují dříve vyřešená zadání.