Найбільший спільний дільник

Найбільший спільний дільник (НСД) двох цілих чисел — це найбільше число, яке ділить обидва числа без залишку. Приклади: НСД(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

Для практичних обчислень використовують інші алгоритми, зокрема алгоритм Евкліда.

Вибір

Швидке практикування шляхом вибору з двох варіантів.

Найбільший спільний дільник

Вибір • середній

Pexeso

Вправа на знаходження пар.

Найбільший спільний дільник

Pexeso • легке

Крок за кроком

Доповнення окремих кроків в рамках комплексної роботи.

Найбільший спільний дільник

Найбільший спільний дільник без застосування степенів

Крок за кроком • середній

Найбільший спільний дільник без застосування степенів

Письмова відповідь

Вправа, в якій ви набираєте відповідь на клавіатурі.

Найбільший спільний дільник

Письмова відповідь • середній

Попередній

Подальший

Вправи

Найбільший спільний дільник

Вибір