Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(НОД(a, b)=НОД(b, a\bmod b)\).

Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).