🔑 Найбільший спільний дільник та взаємно прості числа

Уявіть собі ситуацію: ви маєте кілька предметів і хочете розділити їх на групи так, щоб у кожній було однакова кількість. Яка ж найбільша кількість предметів може бути в кожній групі?
Саме для таких задач у математиці існує поняття найбільшого спільного дільника (НСД).

🔍 Найбільший спільний дільник (НСД) — це найбільше натуральне число, на яке націло ділиться кожне з даних чисел.

✈️ Приклад. Знайдіть найбільший спільний дільник чисел 30 і 45.

🔍 Спосіб 1 (через дільники):
D(30) = {1, 2, 3, 5, 6, 10, 15, 30},
D(45) = {1, 3, 5, 9, 15, 45},
спільні дільники: {1, 3, 5, 15},
👉 найбільший з них — 15.
Отже, НСД(30; 45) = 15.

🔍 Спосіб 2 (через прості множники):
30 = 2 ⋅ 3 ⋅ 5,
45 = 3 ⋅ 3 ⋅ 5,
спільні множники: 3 ⋅ 5 = 15.
👉 НСД(30; 45) = 15.

Відповідь: 15. 🔺

🔍 Взаємно прості числа — це такі числа, спільний дільник яких лише 1.

✈️ Приклад: числа 14 і 25 є взаємно простими, оскільки НСД(14; 25) = 1.

✈️ Зверніть увагу: знаходження НСД часто використовується в реальних задачах — від скорочення дробів до оптимального планування ресурсів.

❓ А ви знали, що існує алгоритм, який називається алгоритмом Евкліда, що дозволяє знаходити НСД навіть для дуже великих чисел без виписування всіх дільників чи розписування простих множників?

🇺🇦@abitmath 🇺🇦@abitblog