Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД, в англоязычной литературе - GCD - Greatest Common Divisor) двух целых чисел.
Для упрощения, ниже будем считать, что .
Время работы алгоритма Евклида составляет O(log a +log b) арифметических операций над натуральными числами.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».