def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a; m,n = x-u*q,y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

b, x, y = egcd(599703852157208324988436697659896404638315905290324375700570316485421693, 2021187385200166516022746434619391941987919206967476592818217288363509)

print "b: " + str(b)
print "x: " + str(x)
print "y: " + str(y)



(michael@rain)~/dev $ python egcd.py
b: 1
x: -3047508293327982779161516622450839163404526801300587435875399397355
y: 904222179681195587324531859318948099549580203141997568283661184044224
(michael@rain)~/dev $
(michael@rain)~/dev $ python egcd.py
b: 1
x: -3047508293327982779161516622450839163404526801300587435875399397355
y: 904222179681195587324531859318948099549580203141997568283661184044224
(michael@rain)~/dev $