Що таке найбільший спільний дільник?

Вміння визначати найбільший спільний дільник — одне з основних для роботи з дробами. НСД може стати в пригоді й для розв’язання лінійних рівнянь.

Що таке найбільший спільний дільник (НСД)

Найбільшим спільним дільником для двох та більше чисел називають максимальне значення, яке ділиться на кожне з цих чисел без остачі.

Для запису цієї конструкції використовується позначення НСД (а; b). Наприклад: найбільшим спільним дільником для чисел 18 та 24 буде число 6. В робочий зошит це записується так: НСД (18; 24) = 6.

Визначення найбільшого спільного дільника (НСД). Методи знаходження

Для швидкого та ефективного виконання завдань на знаходження НСД варто опанувати три алгоритми. Надалі в роботі можна буде робити вибір методу, враховуючи:

кількість чисел;
розмір цих чисел;
власні вподобання.

Репетитор математики допоможе швидше опанувати кожен з алгоритмів для знаходження найбільшого спільного дільника.

Метод множників

Метод множників, або розкладання на прості множники, може використовуватись для знаходження НСД двох та більше чисел.

Суть методу полягає в тому, що кожне з чисел потрібно розкласти на множники. Наступний крок — пошук всіх спільних простих множників для обох чисел. Щоб отримати найбільший спільний дільник, залишиться перемножити всі ці числа.

Метод хоч і є найбільш розповсюдженим та відомим, проте він має свої недоліки. Так, його може бути важко використовувати для чисел, які мають велику кількість простих множників.

Метод послідовних чисел. Таблиця простих чисел

Серед переваг методу послідовних чисел можна зазначити його зрозумілість та простоту використання. Для знаходження НСД можна скористатись таблицею взаємно простих чисел. В цій таблиці знаходяться числа, найбільший спільний дільник яких — одиниця.

Використання алгоритму Евкліда

Алгоритму Евкліда — найбільш досконалий метод знаходження найбільшого спільного дільника. Він дозволяє працювати навіть з великими числами. В його основі лежить низка дій ділення.

Потрібно обрати менше число з тих, НСД яких треба знайти.
Далі слід поділити більше число на менше.
Якщо при діленні отримали остачу, потрібно менше число розділити на остачу.
Далі — першу остачу розділити на другу.

Так слід робити, допоки при діленні не вийде число, яке не має остачі.

Приклали застосування алгоритмів пошуку НСД

Спробуємо знайти найбільший спільний дільник для чисел 24 та 36 методом множників. Розкладаємо 24 на прості множники: 2 х 3 х 4. Розкладаємо 32 на звичайні множники: 3 х 3 х 4. Спільні множники для двох чисел — 3 та 4. 3 х 4 = 12. НСД (24; 36) = 12.

Знайдемо НСД для 11 та 38. Використаємо для цього другий спосіб — таблицю простих чисел. Як бачимо, число 11 є в цій таблиці. Тобто НСД (11; 38) = 1.

Використаємо також алгоритм Евкліда для чисел 36 та 56.

Беремо число 36.
Ділимо: 56 / 36 = 1 (остача 20).
Далі ділимо: 36 / 20 = 1 (остача 16).
Ділимо ще: 20 / 16 = 1 (остача 4).
16 / 4 = 4.

Після ряду дій ділення, ми отримали число без остачі. Отже, НСД (36; 56) = 4.

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