Кстати, я не совсем прав. У Евклида действительно использовалась разность, а не остаток от деления. Но в случае именно Евклида (и более ранних версий нахождения gcd) в качестве входных параметров нельзя было задать нуль, если не ошибаюсь, до Евклида (а возможно и во время него) люди ничего не знали о нуле, его просто не было.
Поэтому нужно либо использовать соответствующие типы, исключающие нуль, либо воткнуть ASSERT.
Ну а та форма которую я привел (и с валидным нулем, и остатком от деления), она много более современная, она уже появилась в нашей эре, аё автор, похоже, Леонардо Пизанский, по прозвищу Фибоначчи. Это 12xx год где-то.