В цій статті освітня платформа Mathema розповість, що таке найбільший спільний дільник (НСД) і як його легко знайти з допомогою алгоритму Евкліда. Також в статті будуть завдання на пошук найбільшого спільного дільника.
Що таке найбільший спільний дільник (НСД)?
Найбільший спільний дільник (НСД) двох або більше чисел — це найбільше число, яке ділить кожне з цих чисел без залишку. Іншими словами, це найбільше число, на яке можуть ділитися всі ці числа одночасно.
Приклад: Розглянемо числа 55 і 132. Найбільший спільний дільник для цих чисел — це 11, оскільки:
- 55 ділиться на 11 (55 ÷ 11 = 5)
- 132 ділиться на 11 (132 ÷ 11 = 12)
Отже, НСД для чисел 55 і 132 дорівнює 11.
Як знайти найбільший спільний дільник (НСД)?
Ось кілька способів знайти НСД. Розглянемо на прикладі чисел 35 і 133.
Випишіть числа на які ділиться перше число:
- Для 35: 1, 5, 7, 35
- Для 133: 1, 7, 19, 133.
- НСД = 7
У цьому приладі бачимо, що обидва числа діляться на 7 та на 1. 7 — найбільшим спільним дільником.
Розкладіть числа на прості множники
Це інший спосіб, який приведе нас до того ж результату:
- 35 = 5 · 7
- 133 = 7 · 19
- НСД = 7
Оберімо трохи складніший приклад і спробуємо розвʼязати його розкладанням на прості множники. Візьмемо числа 154 та 396.
- 154 = 14 · 11 = 2 · 7 · 11
- 396 = 4 · 9 · 11 = 2 · 2 · 3 · 3 · 11
- НСД (154 ; 396) = 2 · 11 = 22
Якщо найбільший спільний дільник для обох чисел 1, то такі числа називаються взаємно простими. Більше про це читайте в нашій статті “Що таке прості числа?”.
Шукаєш репетитора з математики?
Mathema підбере викладача під потреби дитини
Що таке алгоритм Евкліда?
Алгоритм Евкліда — це простий спосіб знайти найбільший спільний дільник (НСД) двох чисел. Ось як це робиться:
- Візьмемо два числа, наприклад 48 і 18. Почнемо з більшого числа.
- Поділимо більше число на менше і знайдемо остачу. Для 48 і 18 остача буде 12 (48 = 18 · 2 + 12).
- Тепер повторимо процес: поділимо 18 на 12. Остача буде 6 (18 = 12 · 1 + 6).
- Продовжуємо ділити, поки остача не стане 0. Останнє число, на яке ми поділимо без остачі і буде НСД.
- В нашому випадку 12 поділиться на 6 без остачі, і остача 0.
- Тому НСД — це 6.
Тобто, за алгоритмом Евкліда ми просто ділимо числа одне на одне, поки не отримуємо остачу 0.
Алгоритм Евкліда був придуманий дуже давно, понад 2000 років тому. Його описав грецький математик Евклід у своїй книзі “Начала” приблизно в 300 році до нашої ери. Це один із найстаріших математичних методів, який досі використовують. Евклід розробив цей алгоритм, щоб вивчати властивості чисел. Навіть сьогодні цей метод залишається важливим у математиці та комп’ютерних науках.
Завдання на пошук НСД
Ось пʼять завдань на пошук найбільшого спільного дільника. Спробуйте розвʼязати їх різними методами а також знайти серед цих чисел всаємно прості.
- Знайдіть НСД чисел 56 і 98.
- Знайдіть НСД чисел 105 і 252.
- Знайдіть НСД чисел 144 і 60.
- Знайдіть НСД чисел 81 і 153.
- Знайдіть НСД чисел 72 і 120.
