GCD using Extended Euclidean
123456789101112
def extended_euclidean(a, b):
if b == 0:
return (a, 1, 0)
else:
gcd, x, y = extended_euclidean(b, a % b)
return (gcd, y, x - (a // b) * y)
a = 161
b = 28
gcd, x, y = extended_euclidean(a, b)
print(f"gcd({a}, {b}) = {gcd} = {x}*{a} + {y}*{b}")
Python
INFO