# egcd.py
# Fig. 6.5 
# input: 13 7 or 7 5
'''
  Extended great common divisor, returns x , y
  and gcd(a,b) so ax + by = gcd(a,b)
'''

def gcd(a,b):
  while b > 0:
    a, b = b, a%b
  return a


def lcm(a, b):
  # https://en.wikipedia.org/wiki/Least_common_multiple
  return a * (b // gcd(a, b))


def egcd(a, b):
  x, x1 = 1, 0
  y, y1 = 0, 1
  g, g1 = a, b
  while g1 > 0:
    q = g // g1
    x, x1 = x1, x - q*x1
    y, y1 = y1, y - q*y1
    g, g1 = g1, g - q*g1
  return g, x, y


def egcdRec(a, b):
  return egRec(a, 1, 0, b, 0, 1)

def egRec(g, x, y, g1, x1, y1):
  if g1 == 0:
    return g, x, y
  else: 
    q = g // g1
    g2 = g - q*g1
    return egRec(g1, x1, y1, g2, x-q*x1, y-q*y1)


# ------------- main ----------------

if __name__ == "__main__":
  a, b = map(int, input("a b? ").split())
  print("gcd == a*x + b*y")
  # g, x, y = egcd(a,b)
  g, x, y = egcdRec(a,b)
  print("gcd ==", g, "; x ==", x, "; y ==", y)