def extended_gcd(a, b):
  """ return (g,v) such that 
      g = gcd(a,b) and
      g == v*a (mod b)"""
  r, s = a, b
  u, v = 1, 0
  while r:
    q = s // r
    r, s = s - q * r, r
    u, v = v - q * u, u
  if s < 0:
    s, v = -s, -v
  return (s, v % b)