В Python математический модуль содержит ряд математических операций, которые могут быть выполнены достаточно быстро. Начиная с версии 3.5 можно использовать встроенную функцию вычисления НОД двух любых целых чисел - math.gcd(a, b)
.
GCD - аббревиатура от Greatest Common Divisor.