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

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

Ответ

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