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

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

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

Візьмемо до уваги другий факт. Якщо одне число більше іншого, то їх найбільший спільний дільник дорівнює найбільшому загальному дільнику для меншого числа з пари, і різниці більшого і меншого. Записується це так: якщо a

Довести, що НОД (a; b) = НСД (a; b - a) можна наступним чином. Нехай b - a = c. Якщо будь-яка кількість ділить a і b, то воно буде ділити без остачі і c. Адже якщо a і b різні, то дільник в них вкладається ціле, але різне число раз. І якщо відняти одне з іншого, то дільник також повинен укладатися ціле число раз в отриману різницю.

Якщо послідовно зменшувати a і b, то рано чи пізно прийдемо до такого значення меншого з них, яке без остачі ділить більшу. Менше в такій парі і буде НСД для початкової пари натуральних чисел. В цьому і полягає алгоритм Евкліда.

Розглянемо на конкретному прикладі. Нехай потрібно знайти НСД (108, 72).

  1. 108 не ділиться на 72. Значить отримуємо пару 72 і 108 - 72 = 36
  2. 72 ділиться без остачі на 36. Значить НСД (108, 72) = 36.

Знайдемо НСД (44, 60):

  1. 60 не ділиться на 44. 60 - 44 = 16
  2. 44 не ділиться на 16. 44 - 16 = 28
  3. 28 не ділиться на 16. 28 - 16 = 12
  4. 16 не ділиться на 12. 16 - 12 = 4
  5. 12 ділиться на 4. Значить НСД (44, 60) = 4

Схожі статті