Алгоритм Евкліда знаходження НСД

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

Візьмемо до уваги факт, що якщо одне натуральне число з пари остачі ділить інше, то їх НОД буде дорівнює меншому з них. Записати це можна так: якщо a / b (остачі), то НСД (a; b) = b.

Візьмемо до уваги другий факт. Якщо одне число більше іншого, то їх найбільший спільний дільник дорівнює найбільшому загальному дільнику для меншого числа з пари, і різниці більшого і меншого. Записується це так: якщо a <b, то НСД (a; b) = НСД (a; 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

Посилання на основну публікацію