42
правки
Изменения
→Стандартный алгоритм Евклида
|statement=<tex>\gcd (0,r) = r</tex> для любого ненулевого <tex>r.</tex>
}}
Далее, оценим асимптотику работы алгоритма.
{{Теорема
|statement=
Алгоритм Евклида работает за <tex>O(\log \max (a, b))</tex>
}}
Доказательство этого факта<ref>[http://mathworld.wolfram.com/EuclideanAlgorithm.html Wolfram MathWorld {{---}} алгоритм Евклида]</ref> достаточно громоздкое, поэтому не будем приводить его здесь.
Проще сформулировать алгоритм Евклида так: если даны натуральные числа <tex>a</tex> и <tex>b</tex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
