def extended_euclid_gcd(a, b):
 if (b == 0):
  return (a, 1, 0)
 q = abs((a % b))
 r = long((a / b))
 (d, k, l) = extended_euclid_gcd(b, q)
 return (d, l, (k - (l * r)))

def extended_euclid_gcd ( a , b ) : if ( b == 0 ) : return ( a , 1 , 0 ) q = abs ( ( a % b ) ) r = long ( ( a / b ) ) ( d , k , l ) = extended_euclid_gcd ( b , q ) return ( d , l , ( k - ( l * r ) ) )
returns a tuple such that d = gcd = ia + jb .