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)