Алгоритм Евклида

Алгоритм Евклида представляет собой удивительно простой поиск наибольшего общего делителя (НОД или gcd).

Выглядит он следующим образом:

Пусть $a$, $b$ - числа для которых нужно найти НОД.

Запишем следующий ряд:

$r_0, r_1, r_2, r_3, r_4, ..., r_n$

Где

$r_0 = a$,

$r_1 = b$,

$r_i = r_{i-2} \pmod {r_{i-1}}, i >= 2$

Этот ряд сходится к нулю, т.к. остаток от деления всегда меньше, чем делитель. Таким образом, $r_n = 0$

Но самое важное, что $r_{n-1} = gcd(a, b)$

Для удобства и скорости вычисления можно предварительно поменять местами $a$, $b$ так чтобы $a > b$. Если этого не сделать, то итераций будет на одну больше. Первая итерация сама поменяет их местами, т.к $a \pmod b = a$ при $a < b$