
def gcd(a, b):
    """Алгоритм Евклида"""
    if a >= b:
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    else:
        a, b = b, a
        return gcd(a, b)


def egcd(a, b):
    """Расширенный алгоритм Евклида"""
    if a >= b:
        if b == 0:
            return (1, 0, a)
        (x, y, _) = egcd(b, a % b)
        return (y, x - (a // b) * y, gcd(a, b))
    else:
        a, b = b, a
        return egcd(a, b)


def print_egcd(a, b):
    """Печать egcd""" # Здесь ещё больше вещей, чем в print_gcd =)
    print(f"НОД({a}, {b}): " + str(egcd(a, b)[2]) + f"\nНОК({a}, {b}): " + str((a * b) // egcd(a, b)[2]))
    print(f"x = {egcd(a, b)[0]}, y = {egcd(a, b)[1]},\nd = {a} * x + {b} * y = {a} * {egcd(a, b)[0]} + {b} * {egcd(a, b)[1]} = " + str(egcd(a, b)[2]))


"""Проверка работы программы"""

print_egcd(5, 25)
print('')
print_egcd(32, 24)
print('')
print_egcd(7, 44)

НОД(5, 25): 5
НОК(5, 25): 25
x = 0, y = 1,
d = 5 * x + 25 * y = 5 * 0 + 25 * 1 = 5

НОД(32, 24): 8
НОК(32, 24): 96
x = 1, y = -1,
d = 32 * x + 24 * y = 32 * 1 + 24 * -1 = 8

НОД(7, 44): 1
НОК(7, 44): 308
x = -3, y = 19,
d = 7 * x + 44 * y = 7 * -3 + 44 * 19 = 1

Расширенный алгоритм Евклида¶

$\textit{Поиск НОДа и НОКа двух чисел, а также линейного разложения НОДа}$¶