Extended Euclidean algorithm
123456789101112
def ext_euclid (a,b):
if (b == 0):
return 1, 0, a
else:
x , y , q = ext_euclid( b , a % b )
x , y = y, ( x - (a // b) * y )
return x, y, q
x,y,q=ext_euclid(3120,17)
print(x)
print(y)
print(q)
Python
INFO