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

Алгоритм Евклида — это способ нахождения наибольшего общего делителя для двух чисел.

Примем во внимание факт, что если одно натуральное число из пары нацело делит другое, то их НОД будет равен меньшему из них. Записать это можно так: если 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).

  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