def euclid(a, b):
'''
Алгоритм Евклида
Возвращает НОД(a, b), где a, b – целые
'''
a = abs(a)
b = abs(b)
while b > 0:
a, b = b, a % b
return a
euclid(88179, 5313)
21
def ext_euclid(a, b):
'''
Расширенный алгоритм Евклида
Возвращает (d, u, v), где d = НОД(a, b) и u*a + v*b = d
'''
u_prev, v_prev = 1, 0
u, v = 0, 1
if a < 0:
a = -a
u_prev = -1
if b < 0:
b = -b
v = -1
while b > 0:
q = a // b
a, b = b, a % b
u_prev, u = u, u_prev - q*u
v_prev, v = v, v_prev - q*v
return a, u_prev, v_prev
a = 88179
b = 5313
d, u, v = ext_euclid(a, b)
print d, u, v
21 62 -1029
u*a + v*b
21