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

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

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

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

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

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

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

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

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар