Алгоритм Евклида для вычисления НОД

#алгоритм #математика

В школьной презентации алгоритм Евклида описан так:


  Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они
не станут равны. Это и есть НОД.


А я привык к такому алгоритму:


Большее число делим на меньшее.
Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
Если есть остаток, то большее число заменяем на остаток от деления.
Переходим к пункту 1.


Откуда взят алгоритм, представленный выше? Обоснован ли он математически?
    

Ответы

Ответ 1

Алгоритм Евклида полностью аналогичен "привычному", за исключением того, что он по
древности своей считает остаток, отнимая по одному меньшему числу от большего, пока
результат не станет меньше ЭТОГО меньшего, а Вы умеете сразу делить с остатком.


Ответ 2

Это и есть тот самый алгоритм, который и применял сам Евклид. Называется он "Геометрический
Алгоритм Евклида"

Согласно Википедии он звучит следующим образом:


  Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший
  и заменим больший отрезок полученной разностью. Повторяем эту
  операцию, пока отрезки не станут равны. Если это произойдёт, то
  исходные отрезки соизмеримы, и последний полученный отрезок есть их
  наибольшая общая мера. Если общей меры нет, то процесс бесконечен


Дополнительно можно посмотреть здесь: "Евклида алгоритм"


Ответ 3

А есть еще и такой вариант -

НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b


ну, а при нечетных - как обычно... :)