Кожен дільник натурального числа  не може бути більшим самого числа , тому число  має скінченне число дільників, які не перевищують .

Серед дільників чисел і  можуть бути однакові, тобто спільні дільники. Очевидно, їх кількість так само є скінченною. Наприклад, числа 30 і 70 мають чотири спільних дільники: 1, 2, 5 і 10. Серед цих дільників є найбільший (в даному випадку 10), його називають найбільшим спільним дільником (НСД) і позначають .

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

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

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

Розглянемо, яким чином він діє. Отже, для початку, розділимо число  на число  із залишком. Позначимо цей залишок через . Якщо , то розділимо  на  із залишком. Нехай – залишок отриманий в результаті другого ділення. Аналогічно, якщо , то розділимо  на  і отримаємо новий залишок . Таким чином, -та ітераці алгориту Евкліда складається з однієї операції ділення із залишком, причому ділене дорівнює залишку отриманому на -й ітерації. Ітераційний процес продовжується до тих пір, поки не отримаємо нульовй залишок. Найбільший спільний дільник двох чисел і , при цьому,  дорівнюватиме  найменшому ненульовому залишку.

Найбільший спільний дільник двох чисел – приклад знаходження:

Знайти НСД чисел 1432 і 41 використовуючи алгоритм Евкліда. Зазначимо, що процедура ділення з залишком, в даному випадку, виглядатиме наступним чином:

Останній ненульовий залишок дорівнює 1, тому .

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

Алгоритм Евкліда блок-схема

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

*