Изменения

}}

{{Лемма

|statement=<tex>\gcd (0,r) = r</tex> для любого ненулевого <tex>r.</tex>

}}

'''return''' <tex>\mathtt{a}</tex>

Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.

===Двоичный алгоритм Евклида===

Идея улучшения: давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.