Алгоритм Евкліда - це спосіб знаходження найбільшого спільного дільника для двох чисел.
Візьмемо до уваги факт, що якщо одне натуральне число з пари без остачі ділить інше, то їх НОД буде дорівнює меншому з них. Записати це можна так: якщо a / b (без остачі), то НСД (a; b) = b.
Візьмемо до уваги другий факт. Якщо одне число більше іншого, то їх найбільший спільний дільник дорівнює найбільшому загальному дільнику для меншого числа з пари, і різниці більшого і меншого. Записується це так: якщо a
Довести, що НОД (a; b) = НСД (a; b - a) можна наступним чином. Нехай b - a = c. Якщо будь-яка кількість ділить a і b, то воно буде ділити без остачі і c. Адже якщо a і b різні, то дільник в них вкладається ціле, але різне число раз. І якщо відняти одне з іншого, то дільник також повинен укладатися ціле число раз в отриману різницю.
Якщо послідовно зменшувати a і b, то рано чи пізно прийдемо до такого значення меншого з них, яке без остачі ділить більшу. Менше в такій парі і буде НСД для початкової пари натуральних чисел. В цьому і полягає алгоритм Евкліда.
Розглянемо на конкретному прикладі. Нехай потрібно знайти НСД (108, 72).
- 108 не ділиться на 72. Значить отримуємо пару 72 і 108 - 72 = 36
- 72 ділиться без остачі на 36. Значить НСД (108, 72) = 36.
Знайдемо НСД (44, 60):
- 60 не ділиться на 44. 60 - 44 = 16
- 44 не ділиться на 16. 44 - 16 = 28
- 28 не ділиться на 16. 28 - 16 = 12
- 16 не ділиться на 12. 16 - 12 = 4
- 12 ділиться на 4. Значить НСД (44, 60) = 4